回溯系列三之字符串与游戏

柔情只为你懂 2022-12-05 10:25 123阅读 0赞

### 文章目录 ###

*   *  字符串中的回溯
     *   *  电话号码的字母组合
         *   *  题目
             *  思想
             *  代码
         *  字母的大小写排列
         *   *  题目
             *  思想
             *  代码
         *  括号生成
         *   *  题目
             *  思想
             *  代码（DFS）
             *  代码（BFS）

## 字符串中的回溯 ##

### 电话号码的字母组合 ###

#### 题目 ####

[电话号码的字母组合][Link 1]

![image-20200909225912255][]

#### 思想 ####

利用回溯的基本思想，将出现的值先进行值先进行数组的记录处理，然后再进行基础的回溯。

#### 代码 ####

public List<String> letterCombinations(String digits) { 
           String [] nums = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            List<String > list = new ArrayList<>();
            if(digits.length()==0)
            return list;
            char [] chars =digits.toCharArray();
            StringBuilder stringBuilder = new StringBuilder();
            dfs(0,chars,list,stringBuilder,nums);
            return  list;
        }
        private  static  void dfs(int start,char[] chars,List<String>list,StringBuilder stringBuilder,String [] nums){ 
            if(start == chars.length){ 
                list.add(stringBuilder.toString());
                return;
            }
            char c= chars[start];
            String temp =nums[c-'0'-2];
            for(int i =0 ;i<temp.length();i++){ 
                stringBuilder.append(temp.charAt(i));
                dfs(start+1,chars,list,stringBuilder,nums);
                stringBuilder.deleteCharAt(stringBuilder.toString().length()-1);
            }
        }

### 字母的大小写排列 ###

#### 题目 ####

[784-字母的大小写排列][784-]  
![image-20200909230902892][]

#### 思想 ####

利用基本回溯，用记录值记录出现的是字母的字符串，并且适当做回溯处理。

#### 代码 ####

public List<String> letterCasePermutation(String S) { 
          List<String> list = new ArrayList<>();
            if(S.length() == 0)
                return  list;
            char [] chars =S.toCharArray();
            dfs(0,chars,list);
            return  list;
        }
        private  static void dfs(int index,char [] chars,List<String> list){ 
            list.add(String.valueOf(chars));
          // 标志。
            char temp = '0';
            if(index == chars.length)
                return;
            for(int i= index;i<chars.length;i++){ 
               if(chars[i]>='A')
               { 
                   temp =chars[i];
                   chars[i] = (char) (chars[i]<'a'?chars[i]+32:chars[i]-32);
                   dfs(i+1,chars,list);
                   chars[i]= temp;
               }
            }
        }

### 括号生成 ###

#### 题目 ####

[22-括号生成][22-]

![image-20200909231441654][]

#### 思想 ####

`DFS`： 对于深度优先来说，记录左右括号的个数，在左右括号都是0的时候记录下来。

`BFS`：自行定义数据结构，进行处理。

#### 代码（DFS） ####

public List<String> generateParenthesis(int n) { 
    List<String> list = new ArrayList<>();
        if(n == 0){ 
            return  list;
        }
        dfs("",n,n,list);
        return  list;
        }
        private  static  void dfs(String curChar,int left,int right,List<String> list){ 
            if(left == 0 && right == 0){ 
                list.add(curChar);
                return;
            }
            if(left>right)
                return;
            if(left>0){ 
                dfs(curChar+"(",left-1,right,list);
            }
            if(right>0)
            { 
                dfs(curChar+")",left,right-1,list);
            }
        }

#### 代码（BFS） ####

class Node{ 
    
        private  String str;
    
            private  int left;
    
            private  int right;
    
            public Node(String str,int left,int right){ 
                this.str = str;
                this.left = left;
                this.right = right;
            }
        }
    public List<String> generateParenthesis(int n) { 
            Queue<Node> queue = new LinkedList<>();
            List<String> list = new ArrayList<>();
            queue.offer(new Node("",n,n));
            while(!queue.isEmpty()){ 
                Node temp = queue.poll();
                if(temp.right ==0 && temp.left == 0){ 
                    list.add(temp.str);
                }
              if(temp.left >0){ 
                    queue.offer(new Node(temp.str+"(",temp.left-1,temp.right));
                }
                if(temp.right >0 && temp.left<temp.right)
                { 
                    queue.offer(new Node(temp.str+")",temp.left,temp.right-1));
                }
            }
            return  list;
        }

(未完待续…)

[Link 1]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[image-20200909225912255]: /images/20221123/cfc96c4632a94699b324d6ffe90da192.png
[784-]: https://leetcode-cn.com/problems/letter-case-permutation/
[image-20200909230902892]: /images/20221123/10c3a9587e1e4af99af4721830e2fdbb.png
[22-]: https://leetcode-cn.com/problems/generate-parentheses/
[image-20200909231441654]: /images/20221123/ea1f31a23db24e14be1423d784383509.png