DFS+回溯

DFS

电话号码的字母组合

/**给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
*/
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // 2 的映射 abc 存到临时表+固定表中  固定表 = 临时表
        if(digits.empty()) return vector<string>();
        string str[8] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        
        vector<string>ch(1,"");
        for(auto x : digits) {// 2 3
            vector<string>now;
            for(auto s : str[x - '2']){ // 123 456
                for(auto z : ch)
                	now.push_back(z+s); 
            }
            ch = now;
        }
        return ch;
    }
};

单词搜索

/**
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
*/
class Solution {
public:
    int m , int n;
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
     bool exist(vector<vector<char>>& board, string word) {
         if(!board.empyt() || board[0].empty()) return false;
         m = board.size(), n = board[0].size();
         
         for(int i = 0; i < n; i++){
             for(int j = 0; j < m; j++){
                 if(dfs(board,i,j,word,len))
                     return true;
             }
         }
         return false;
     }
    bool dfs(vector<vector<char>>& board, int x, int y, stirnt& word, int len){
        if(board[i][j] != word[len]) return false;
        if(len == word.size() -1) return true;
        
        board[i][j] = '*';
        for(int i = 0 ; i< 4; i++)
        {
            int xi = x + dx[i], yi = y + dy[i];
            if(xi >=0 && xi < n && yi >=0 && yi < n){
                if(dfs(board,xi,yi,word,len+1))
                    return true;
            }
        }
        return false;
    }
};