深度优先遍历(dfs)

回溯

LeetCode22

​ 本题要求生成给定数量的”()”，问有多少种生成方案。比如：要求生成3对括号，那么生成结果可以是”()()()”、”((()))”、”(()())”。

​ 解决本题的关键在于需要保证在生成”)”时，在此之前至少有一个未被配对的”(“。因此我dfs的主要参数有已使用的”(“数量，未被配对的”(“数量。接下来在生成”(“时只需保证”(“的数量还未使用完；生成”)”时只需保证在此之前至少有一个未被配对的”(“。

​ 实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private List<String>res = new ArrayList<>();
    private int leftNum;
    public List<String> generateParenthesis(int n) {
        char s[] = new char[2 * n];
        leftNum = n;

        dfs(0,0,0,s);

        return res;
    }

    public void dfs(int u,int leNum,int noCoupleNum,char s[]){
        if(u == 2 * leftNum){
            String str = new String(s);
            res.add(str);
        }
		//保证"("的数量还未使用完
        if(leNum < leftNum){
            s[u] = '(';
            dfs(u + 1,leNum + 1,noCoupleNum + 1,s);
        }
        //在此之前至少有一个未被配对的"("
        if(noCoupleNum > 0){
            s[u] = ')';
            dfs(u + 1,leNum,noCoupleNum - 1,s);
        }
    }
}

LeetCode131

​ 本题要求对给定字符串进行分割，使得每个子串都是回文串。

​ 解决方法就是直接枚举每个子串是否是回文串。模拟样例：s=”aab”.

1
2
3
4
5
6
7
8
9
10
11
12
13
i = 0,j = i = 0,子串为"a"是回文串加入path中,path={"a"}
	i = 1,j = i = 1,子串为"a"是回文串加入path中,path={"a","a"}
		i = 2,j = i = 2,子串为"b"是回文串加入path中,path={"a","a","b"}
			i = 3 = s.length(),将path加入res中,回溯,path={"a","a"}
         i = 2,j = 3 > s.length() - 1,回溯,path={"a"}
    i = 1,j = 2,子串为"ab"不是回文串
    i = 1,j = 3 = s.length() - 1,回溯,path={}
i = 0,j = 1,子串为"aa"是回文串加入path中,path={"aa"}
	i = 2,j = i = 2,子串为"b"是回文串加入path中,path={"aa","b"}
		i = 3 = s.length(),将path加入res中,回溯,path={"aa"}
	i = 2,j = 3 > s.length() - 1,回溯,path={}
i = 0,j = 2,子串为"aab"不是回文串
i = 0,j = 3 > s.length() - 1,至此,递归结束

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private List<List<String>>res;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        List<String>path = new ArrayList<>();
        dfs(0,s,path);

        return res;
    }
	//判定是否为回文串
    public boolean isPalindrome(int left,int right,String s){
        while(left < right){
            if(s.charAt(left++) != s.charAt(right--)){
                return false;
            }
        }
        return true;
    }

    public void dfs(int i,String s,List<String>path){
        if(i == s.length()){
            res.add(new ArrayList<>(path));
        }

        for(int j = i; j < s.length(); j ++){
            if(isPalindrome(i,j,s)){
                path.add(s.substring(i,j + 1));
                dfs(j + 1,s,path);
                path.remove(path.size() - 1);
            }
        }
    }
}