Backtracking
113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ]
树的题目在做 backtracking 的时候要注意的是if (!node->right && !node->left && cur_sum + node->val == sum) 条件的判断, 如果直接判断 null 的话会出现左右子树判断两次的情况, 导致重复结果.
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> slu;
if (!root) return res;
dfs(root, 0, sum, res, slu);
return res;
}
void dfs(TreeNode* node, int cur_sum, int sum, vector<vector<int>>& res, vector<int>& slu) {
if (!node) return;
if (!node->right && !node->left && cur_sum + node->val == sum) {
res.push_back(slu);
res.back().push_back(node->val);
return;
}
slu.push_back(node->val);
dfs(node->left, cur_sum + node->val, sum, res, slu);
dfs(node->right, cur_sum + node->val, sum, res, slu);
slu.pop_back();
}
};
126. Word Ladder II
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time Each intermediate word must exist in the word list For example,
Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]Note: All words have the same length. All words contain only lowercase alphabetic characters.
class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
unordered_map<string, unordered_set<string>> traces;
unordered_set<string> set1 {start};
unordered_set<string> set2 {end};
bfs_traces(set1, set2, dict, traces, false);
vector<string> slu{start};
vector<vector<string>> res;
get_paths(traces, slu, res, start, end);
return res;
}
void bfs_traces(unordered_set<string> set1, unordered_set<string> set2, unordered_set<string> &dict,
unordered_map<string, unordered_set<string>>& traces, bool reversed) {
if (set1.size() > set2.size()) return bfs_traces(set2, set1, dict, traces, !reversed);
if (set1.size() == 0) return;
for (auto word : set1) dict.erase(word);
bool done = false;
unordered_set<string> nextLevel;
for (auto str : set1) {
for (size_t i = 0; i < str.length(); ++i) {
string next = str;
for (char c = 'a'; c <= 'z'; ++c) {
next[i] = c;
if (str[i] == c || dict.find(next) == dict.end()) continue;
string key = reversed ? next : str;
string val = reversed ? str : next;
traces[key].insert(val);
if (set2.find(next) != set2.end()) {
done = true;
}
if (!done) nextLevel.insert(next);
}
}
}
if (!done) return bfs_traces(set2, nextLevel, dict, traces, !reversed);
}
void get_paths(unordered_map<string, unordered_set<string>>& traces, vector<string>& slu,
vector<vector<string>>& res, string start, string end) {
if (start == end) {
res.push_back(slu);
return;
}
for (auto word : traces[start]) {
slu.push_back(word);
get_paths(traces, slu, res, word, end);
slu.pop_back();
}
}
};
131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ]
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<string> slu;
vector<vector<string>> res;
dfs(s, res, slu, 0);
return res;
}
void dfs(const string& s, vector<vector<string>>& res, vector<string>& slu, int index) {
if (index == s.size()) {
res.push_back(slu);
return;
}
for (int i = 1; i + index <= s.size(); ++i) {
string cur = s.substr(index, i);
if (!isPalindrome(cur)) continue;
slu.push_back(cur);
dfs(s, res, slu, index + i);
slu.pop_back();
}
}
bool isPalindrome(const string& s) {
int len = s.size();
if (len <= 1) return true;
int i = 0;
int j = len - 1;
while (i < j) {
if (s[i++] != s[j--]) return false;
}
return true;
}
};
17. Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits == "") return {};
vector<string> letters{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
int len = digits.size();
vector<string> res;
letterCombinehelper(digits, 0, "", res, letters);
return res;
}
void letterCombinehelper(string digits, int k, string str, vector<string>& res, vector<string>& dicts) {
if (k == digits.size()) {
res.push_back(str);
return;
}
int digit = digits[k] - '0';
for (int i = 0; i < dicts[digit].size(); ++i) {
letterCombinehelper(digits, k + 1, str + dicts[digit][i], res, dicts);
}
}
};
22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
backtrack(res, 0, 0, "", n);
return res;
}
void backtrack(vector<string>& res, int left, int right, string slu, int n) {
if (slu.size() == n*2) {
res.push_back(slu);
return;
}
if (right > left) return;
if (left < n) {
backtrack(res, left + 1, right, slu + "(", n);
}
if (right < left) {
backtrack(res, left, right + 1, slu +")", n);
}
}
};
37. Sudoku Solver
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
vector<pair<int, int>> empty_cell;
for (size_t i = 0; i < board.size(); i++) {
for (size_t j = 0; j < board[0].size(); j++) {
if (board[i][j] == '.') {
empty_cell.push_back(make_pair(i, j));
}
}
}
int num = empty_cell.size();
fill(board, 0, num, empty_cell);
}
bool fill(vector<vector<char>>& board, int cnt, int total, vector<pair<int, int>> emptys) {
if (cnt == total) {
return true;
}
int x = emptys[cnt].first;
int y = emptys[cnt].second;
for (char c = '1'; c <= '9'; ++c) {
if (isValid(x, y, board, c)) {
board[x][y] = c;
if (fill(board, cnt + 1, total, emptys)) {
return true;
}
board[x][y] = '.';
}
}
return false;
}
bool isValid(int x, int y, vector<vector<char>>& board, char value) {
for (int i = 0; i < board.size(); ++i) {
if (board[i][y] == value || board[x][i] == value) return false;
}
int row = (x / 3) * 3;
int col = (y / 3) * 3;
for (int i = row; i < row + 3; ++i) {
for (int j = col; j < col + 3; ++j) {
if (i != x && j != y && board[i][j] == value) return false;
}
}
return true;
}
};
79. Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example, Given board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
size_t m = board.size();
if (!m) return false;
size_t n = board[0].size();
if (!n) return false;
// vector<vector<bool>> visited(m , vector<bool>(n));
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (board[i][j] == word[0] && dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& board, const string& word, int x, int y, int index) {
if (index > word.size() || board[x][y] != word[index]) return false;
if (index == word.size() -1 && board[x][y] == word[index]) return true;
board[x][y] = '\0';
vector<int> steps{0, 1, 0, -1, 0};
for (int i = 0; i < steps.size() - 1; ++i) {
int xi = x + steps[i];
int yi = y + steps[i+1];
if (xi >= 0 && xi < board.size() && yi >= 0 && yi <= board[0].size()) {
if (dfs(board, word, xi, yi, index + 1)) {
board[x][y] = word[index];
return true;
}
}
}
board[x][y] = word[index];
return false;
}
};
140. Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
class Solution { // backtracking.
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
canBreak(s, "", wordDict);
return ret;
}
bool canBreak(string s, string t, unordered_set<string>& wordDict) {
if (!s.length()) {
ret.push_back(t);
return true;
}
for (size_t i = 1; i <= s.length(); ++i) {
string word = s.substr(0, i);
if(wordDict.find(word) != wordDict.end()) {
int len = t.length();
if (len>0)
t += ' ';
t += word;
if (!canBreak(s.substr(i), t, wordDict)) {
// t = t.substr(0, len);
return false;
}
t = t.substr(0, len);
}
}
return true;
}
private:
vector<string> ret;
unordered_map<string, vector<string>> dp;
};
291 Word Pattern II
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples:
pattern = "abab", str = "redblueredblue" should return true. pattern = "aaaa", str = "asdasdasdasd" should return true. pattern = "aabb", str = "xyzabcxzyabc" should return false.Notes:
You may assume both pattern and str contains only lowercase letters.
class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> p2str;
unordered_map<string, char> str2p;
bool res = false;
dfs(pattern, str, 0, 0, p2str, str2p, res);
return res;
}
void dfs(string& pattern, string& str, int i, int j, unordered_map<char, string>& p2str, unordered_map<string, char>& str2p, bool& res) {
if (res) return;
if (i == pattern.size() && j == str.size()) {
res = true;
return;
}
if (i >= pattern.size() || j >= str.size()) return;
if (p2str.find(pattern[i]) == p2str.end()) {
for (int k = j; k < str.size(); ++k) {
string s = str.substr(j, k - j + 1);
if (str2p.find(s) != str2p.end()) continue;
str2p[s] = pattern[i];
p2str[pattern[i]] = s;
dfs(pattern, str, i + 1, k + 1, p2str, str2p, res);
str2p.erase(s);
p2str.erase(pattern[i]);
}
} else {
string target = p2str[pattern[i]];
if (str.substr(j, target.size()) != target) return;
if (str2p[target] != pattern[i]) return;
dfs(pattern, str, i + 1, j + target.size(), p2str, str2p, res);
}
}
};
294 Flip Game II
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up: Derive your algorithm's runtime complexity.
class Solution {
public:
bool canWin(string s) {
if (s.size() < 2) return false;
bool canwin = can_win(s);
return canwin;
}
bool can_win(string& s) {
for (size_t i = 1; i < s.size(); i++) {
if (s[i-1] == '+' && s[i] == '+') {
s[i-1] = '-';
s[i] = '-';
bool wins = !can_win(s);
s[i-1] = '+';
s[i] = '+';
if (wins) return true;
}
}
return false;
}
};
301. Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
"()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""]
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
vector<string> allres;
int max_len = 0;
std::function<void(string, int, int, int)> dfs = [&](string cur, int pos, int left, int right) {
if (left == right && cur.size() >= max_len) {
allres.push_back(cur);
max_len = cur.size();
}
for (int i= pos; i < s.size(); ++i) {
if (i != pos && s[i] == s[i-1]) continue;
if (s[i] == '(') dfs(cur+s[i], i+1, left+1, right);
else if (s[i] == ')' && left > right) dfs(cur+s[i], i + 1, left, right+1);
else if (s[i] != ')') dfs(cur+s[i], i + 1, left, right);
}
};
dfs("", 0, 0, 0);
for (auto str : allres) {
if (str.size() >= max_len) res.push_back(str);
}
return res;
}
};
320 Generalized Abbreviation
Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
class Solution {
public:
vector<string> generateAbbreviations(string word) {
vector<string> res;
genAbbreviations(word, "", false, 0, 0, res);
return res;
}
void genAbbreviations(string word, string slu, bool isPrevNum,
int index, int preNum, vector<string>& res) {
if (index == word.size()) {
if (isPrevNum) slu += to_string(preNum);
res.push_back(slu);
return;
}
if (isPrevNum) {
genAbbreviations(word, slu, true, index + 1, preNum + 1, res);
genAbbreviations(word, slu+to_string(preNum) +
word[index],false, index+1, 0, res);
} else {
genAbbreviations(word, slu, true, index + 1, 1, res);
genAbbreviations(word, slu + word[index], false, index +
1, preNum + 1, res);
}
}
};
Measure with defective jugs (EPI)
backtracking 解法, cache 不可以的情况, 时间复杂度: O((L+1)(H+1)N) : 每次check 有N个CheckFeasibleHelper call, 因为cache了结果, 所以最坏的情况就是 (L+1)(H+1)个recursive call
struct Jug {
int low, high;
};
struct VolumeRange {
int low, high;
bool operator==(const VolumeRange& that) const {
return low == that.low && high == that.high;
}
};
struct HashVolumeRange {
size_t operator()(const VolumeRange& p) const {
return hash<int>()(p.low) ^ hash<int>()(p.high);
}
};
bool CheckFeasible(const vector<Jug>& jugs, int L, int H) {
unordered_set<VolumeRange, HashVolumeRange> cache;
return CheckFeasibleHelper(jugs, L, H, &cache);
}
bool CheckFeasibleHelper(const vector<Jug>& jugs, int L, int H,
unordered_set<VolumeRange, HashVolumeRange>* c) {
if (L > H || c->find({L, H}) != c->cend() || (L < 0 && H < 0)) {
return false;
}
// Checks the volume for each jug to see if it is possible.
for (const Jug& j : jugs) {
if ((L <= j.low && j.high <= H) || // Base case: j is contained in [L, H]
CheckFeasibleHelper(jugs, L - j.low, H - j.high, c)) {
return true;
}
}
c->emplace(VolumeRange{L, H}); // Marks this as impossible.
return false;
}