剑指offer专项突击版第29天

剑指 Offer II 085. 生成匹配的括号

递归指数型枚举（二叉树结构），在 $n\ast 2$ 个位置上放 ‘(’ 或 ‘)’ ，出现的序列肯定都不同，值得注意的是在放 ‘)’ 时，前面的 ‘(’ 数量要大于它。

class Solution {
public:
    vector<string> res;
    string tmp;
    vector<string> generateParenthesis(int n) {
        string tmp;    
        dfs(n*2,0,0);
        return res;
    }
    void dfs(int x, int l, int r) {
        if(x == 0) {
            if(l == r) res.emplace_back(tmp);
            return;
        }        
        tmp.push_back('(');
        dfs(x-1,l+1,r);
        tmp.pop_back();
        if(l > r) {
            tmp.push_back(')');
            dfs(x-1, l, r+1);
            tmp.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

剑指 Offer II 086. 分割回文子字符串

朴素做法每个栈帧要处理的是：截取字符串 $str$ 从 $s$ 第 $x$ 字符开始共截取 $1$ 至 $s.size()-x$ 位。分别判断其是否为回文字符串。若为回文字符串则继续递归下去，反之执行下次循环。

class Solution {
public:
    vector<vector<string>> res;
    vector<string> tmp;
    vector<vector<string>> partition(string s) {
        dfs(0,s);
        return res;
    }
    bool check(string &s) {
        for(int i = 0; i < s.size()/2; i++)
            if(s[i] != s[s.size()-1-i]) return false;
        return true;    
    }
    void dfs(int x, string &s) {
        if(x == s.size()) {
            res.emplace_back(tmp);
            return;
        }
        for(int i = 1; i <= s.size()-x; i++) { //i为截取位数
            string str = s.substr(x,i); //第x位开始，截取i个字符
            if(!check(str)) continue;
            tmp.emplace_back(str);
            dfs(x+i, s);
            tmp.pop_back();
        }
    }
};
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

上述方法会出现多次重复切割字符串并判断回文串，可使用 DP 预处理对其进行优化。

class Solution {
private:
    vector<vector<int>> f;
    vector<vector<string>> ret;
    vector<string> ans;
    int n;

public:
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(ans);
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }
};
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
34
35
36

将第一种方法优化方式换为记忆化搜索

class Solution {
private:
    vector<vector<int>> f;
    vector<vector<string>> ret;
    vector<string> ans;
    int n;

public:
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(ans);
            return;
        }
        for (int j = i; j < n; ++j) {
            if (isPalindrome(s, i, j) == 1) {
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }

    // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
    int isPalindrome(const string& s, int i, int j) {
        if (f[i][j]) {
            return f[i][j];
        }
        if (i >= j) {
            return f[i][j] = 1;
        }
        return f[i][j] = (s[i] == s[j] ? isPalindrome(s, i + 1, j - 1) : -1);
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n));

        dfs(s, 0);
        return ret;
    }
};
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
34
35
36
37
38
39
40
41

---

剑指 Offer II 087. 复原 IP

坑：这题给了个错误的数据范围（0 <= s.length <= 3000）让我误解了题意。

正确的理解：其实 $s$ 只能表示一个 $IP$ 地址，而且要用完全部的字符。

1. 那么就好办了，递归4个深度，每个栈帧在保证 $s$ 字符够用的情况下切割 $1$ 至 $3$ 个字符。
2. 然后拿去判断是否符合 $IP$ 数字格式，若符合接着递归下去，反之回溯。
3. 当然了，拼凑够了 $IP$ 但是字符没用完 和 字符用完了还未拼凑够 $IP$ 这两种情况是要回溯的。
4. 直到拼凑好 $IP$ 并且同时使用完了 $s$ 的字符就是正确答案之一。

class Solution {
public:
    vector<string> res;
    vector<string> tmp;
    vector<string> restoreIpAddresses(string s) {
    	if(s.size() > 12 || s.size() < 4) return res;
        dfs(0,s);
        return res;
    }

    bool check(string &str) {
        if(str.size() > 1 && str[0] == '0' || str.empty()) return false;
        int num = stoi(str);
        return num >= 0 && num <= 255;
    }

    void dfs(int x, string &s) {
        if(x == s.size() && tmp.size() == 4) {
            string str;
            for(int i = 0; i < 4; i++) {
                str += tmp[i];
                if(i < 3) str += '.';
            }   
            res.emplace_back(str);
            return;
        } else if(x == s.size() || tmp.size() == 4) {
            return;
        }

        for(int i = 1; i <= 3 && x+i-1 < s.size(); i++) {
            string str = s.substr(x,i);
            if(!check(str)) return;
            tmp.emplace_back(str);
            dfs(x+i, s);
            tmp.pop_back();
        }

    }
};
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
34
35
36
37
38
39