算法基础/递归回溯

1.17. 电话号码的字母组合

题目描述：

示例：

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

解答描述：

该题要找到所有电话号码的字母组合，采用递归+回溯的方式。

先用一个vector<string>来存储每个数字和字母的匹配，注意数组是从0开始，0和1要初始化为空。

然后对word的每一个位置，递归尝试每一个可能的字母，然后回溯，当位置等于digits.size()时，递归结果，压入结果数组。

代码：

class Solution {
public:
    vector<string> ans;
    string temp;
    //数字和字母的对应，注意数组从0开始，所以0,1都初始化为空
    vector<string> tele={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    //依次处理每个位置
    void DFS(string digits,int index)
    {
        if(index==digits.size())
        {
            ans.push_back(temp);
            return;
        }
        int num=digits[index]-'0';
        for(int i=0;i<tele[num].size();i++)
        {
            temp.push_back(tele[num][i]);
            DFS(digits,index+1);
            temp.pop_back();
        }
        
    }
    vector<string> letterCombinations(string digits) {
        
        int n=digits.size();
        if(n==0)
        {
            return ans;
        }
        DFS(digits,0);
        return ans;  
    }
};

2.22. 括号生成

题目描述：

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

解答描述：

该题要找到所有可能的有效的括号组合。首先明确有效的括号组合，左右括号数目要都==n并且成对。

递归+回溯实现

1）当总括号个数到达2n的时候，递归结束

2）当左括号数小于n的时候表示还可以加入一个左括号

3）当右括号数小于左括号数时表示还可以加入一个右括号

代码：

class Solution {
public:
    vector<string> ans;
    string temp;
    void DFS(int n,int index,int left,int right)
    {
        if(index==2*n)
        {
            ans.push_back(temp);
            return;
        }
        //当左括号数小于n时可以加入一个左括号
        if(left<n)
        {
            temp+="(";
            DFS(n,index+1,left+1,right);
            temp.pop_back();
        }
        //当右括号数少于左括号数时，可以加入一个右括号
        if(right<left)
        {
            temp+=")";
            DFS(n,index+1,left,right+1);
            temp.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        DFS(n,0,0,0);
        return ans;
    }
};

3.79. 单词搜索

题目描述：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例：

解答描述：

非常典型的二维矩阵的DFS，见注释

代码：

class Solution {
public:
    bool flag=false;
    
    void DFS(vector<vector<char>>& board,vector<vector<int>>& visited,string word,int index,int s,int t)
    {
        if(index==word.size())
        {
            flag=true;
            return;
        }
        if(s>=0 && s<board.size() && t>=0 && t<board[0].size() && board[s][t]==word[index] && !visited[s][t])
        {
            visited[s][t]=1;
            DFS(board,visited,word,index+1,s+1,t);
            DFS(board,visited,word,index+1,s-1,t);
            DFS(board,visited,word,index+1,s,t+1);
            DFS(board,visited,word,index+1,s,t-1);
            visited[s][t]=0;//回溯的时候要把 vis还原
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        int n=word.size();
        int rows=board.size();
        int cols=board[0].size();
        vector<vector<int>> visited(rows,vector<int>(cols,0));//因为每个数不允许重复使用，用vis标记是否被用过
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(board[i][j]==word[0])
                {
                    DFS(board,visited,word,0,i,j);
                }
            }
        }
        return flag;
    }
};