目錄
- Word Squares
- Combination Sum
- Combination Sum II
425. Word Squares
Given a set of words (without duplicates), find all word squares you can build from them.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.
b a l l
a r e a
l e a d
l a d y
Note:
There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.
Example 1:
Input:
["area","lead","wall","lady","ball"]
Output:
[
[ "wall",
"area",
"lead",
"lady"
],
[ "ball",
"area",
"lead",
"lady"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
題目大意：給定一組無(wú)重復(fù)的單詞贪染，要求選出幾個(gè)單詞肢专，組成一個(gè)單詞square棚饵，橫著讀和縱著讀的內(nèi)容相同蔼囊。
解題思路：用前綴表達(dá)式記錄擁有特定前綴的單詞，再用深度優(yōu)先搜索在滿足前綴條件的單詞中進(jìn)行搜索播玖。
//(DFS, backtrace + Prefix tree)
struct TrieNode {
TrieNode(){}
~TrieNode() {}
shared_ptr<TrieNode> next[26];
vector<string> words; //words in dict that have the prefix
// for this node
};
void insertWS(const string &word, shared_ptr<TrieNode> node) {
for (auto const c : word) {
int idx = c - 'a'; //get idx of node for c
if (node->next[idx] == nullptr) {
//create new trie node
node->next[idx] = make_shared<TrieNode>();
}
// move to prefix tree(trie) node with c
node = node->next[idx];
// word is one with prefix contained in node
node->words.push_back(word);
}
}
vector<string> findCandidates(shared_ptr<TrieNode> node, const string &prefix) {
for (auto const & c : prefix) {
int idx = c - 'a';
if (node->next[idx] == nullptr) {
return {};
}
node = node->next[idx]; //level-by-level, search the node for input prefix
}
return node->words; //return a copy of words with prefix
}
void wordSquaresDFS(shared_ptr<TrieNode> node, const int N, vector<string> &path, vector<vector<string>> &ans) {
size_t newIdx = path.size();
if ((int)newIdx == N) {
//if path is long enough, save into ans
ans.push_back(path);
return;
}
string prefix;
//path length must be shorter than word length
for (auto const & word : path) {
//get the newIdx-th column
prefix += word[newIdx];
}
//take the newIdx-th colum as the new row, find all candidates
// words that contain the row as prefix
vector<string> candidates = findCandidates(node, prefix);
for (auto const & candidate : candidates) {
//choose and un-choose one candidate
path.push_back(candidate);
wordSquaresDFS(node, N, path, ans); //advance to next level
path.pop_back(); //un-choose before return
}
}
vector<vector<string>> wordSquares(vector<string>& words) {
vector<vector<string>> ans;
if (words.size() == 0) {
return ans;
}
// build the trie tree
const int N = (int)words.at(0).size();
auto root = make_shared<TrieNode>();
for (auto const & word : words) {
insertWS(word, root);
}
// DFS
vector<string> path;
for (auto const & word : words) {
path.push_back(word);
wordSquaresDFS(root, N, path, ans);
path.pop_back();
}
return move(ans);
}
void WordSquares() {
cout << "WordSquares" << endl;
auto anss = wordSquares(vector<string>{ "area","lead","wall","lady","ball" });
for (auto & ans : anss) {
Print(ans);
}
}
39. Combination Sum
Medium
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
題目大意：給定一個(gè)數(shù)組肉津，要從數(shù)組中選幾個(gè)數(shù)，使之和等于一個(gè)目標(biāo)值迅箩，數(shù)組中每個(gè)數(shù)都可以被選任意多次。
解題思路：利用深度優(yōu)先搜索处铛，對(duì)數(shù)組中的每個(gè)數(shù)一一“選中”饲趋，測(cè)試哪一個(gè)分支滿足條件拐揭，保留滿足條件的分支。
class Solution {
void combinationSumDFS(const vector<int>& candidates, vector<int>& path, int target, int start, vector<vector<int>> &ans) {
if (target < 0) return;
if (target == 0) {ans.push_back(path); return;}
for (int i = start; i < candidates.size(); ++i) {
path.push_back(candidates[i]);
combinationSumDFS(candidates, path, target - candidates[i], i, ans);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
combinationSumDFS(candidates, path, target, 0, ans);
return move(ans);
}
};
測(cè)試一下奕塑，
Success
Details
Runtime: 8 ms, faster than 99.33% of C++ online submissions for Combination Sum.
Memory Usage: 9.5 MB, less than 80.12% of C++ online submissions for Combination Sum.
40. Combination Sum II
Medium
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
題目大意：和上一題基本相同堂污，有差別的在于，數(shù)組中的每個(gè)元素都只能被選中一次龄砰。
解題思路：加一個(gè)記錄當(dāng)前數(shù)組最近“選中”位置的變量盟猖。
class Solution {
void combinationSumDFS(const vector<int>& candidates, vector<int>& path, int target, int start, vector<vector<int>> &ans) {
if (target == 0) {
sort(path.begin(), path.end());
if (find(ans.begin(), ans.end(), path) == ans.end()) {
ans.push_back(path);
}
return;
}
else if (target < 0) {
return;
}
// DFS search range
for (int i = start; i < (int)candidates.size(); i++) {
path.push_back(candidates[i]);
combinationSumDFS(candidates, path, target - candidates[i], i + 1, ans);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
combinationSumDFS(candidates, path, target, 0, ans);
return move(ans);
}
};
測(cè)試一下，
Success
Details
Runtime: 44 ms, faster than 15.78% of C++ online submissions for Combination Sum II.
Memory Usage: 9 MB, less than 81.12% of C++ online submissions for Combination Sum II.
