天天看点
返回

leetcode回溯算法中字符串的处理——9,131，306,842，

题目93

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"

输出: ["255.255.11.135", "255.255.111.35"]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/restore-ip-addresses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

IP地址由32位二进制数组成，为便于使用，常以XXX.XXX.XXX.XXX形式表现，每组XXX代表小于或等于255的10进制数。所以说IP地址总共有四段，每一段可能有一位，两位或者三位，范围是[0, 255]，题目明确指出输入字符串只含有数字，所以当某段是三位时，我们要判断其是否越界（>255)，还有一点很重要的是，当只有一位时，0可以成某一段，如果有两位或三位时，像 00， 01， 001， 011， 000等都是不合法的，所以我们还是需要有一个判定函数来判断某个字符串是否合法。。根据目前刷了这么多题，得出了两个经验， 一是只要遇到字符串的子序列或配准问题首先考虑动态规划DP，二是只要遇到需要求出所有可能情况首先考虑用递归 。这道题并非是求字符串的子序列或配准问题，更符合第二种情况，所以我们要用递归来解。我们用k来表示当前还需要分的段数，如果k = 0，则表示三个点已经加入完成，四段已经形成，若这时字符串刚好为空，则将当前分好的结果保存。若k != 0, 则对于每一段，我们分别用一位，两位，三位来尝试，分别判断其合不合法，如果合法，则调用递归继续分剩下的字符串，最终和求出所有合法组合，

代码： 

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        restore(s, 4, "", res);
        return res;
    }
    void restore(string s, int k, string out, vector<string> &res) {
        if (k == 0) {
            if (s.empty()) res.push_back(out);
        }
        else {
            for (int i = 1; i <= 3; ++i) {
                if (s.size() >= i && isValid(s.substr(0, i))) {
                    if (k == 1) restore(s.substr(i), k - 1, out + s.substr(0, i), res);
                    else restore(s.substr(i), k - 1, out + s.substr(0, i) + ".", res);
                }
            }
        }
    }
    bool isValid(string s) {
        if (s.empty() || s.size() > 3 || (s.size() > 1 && s[0] == '0')) return false;
        int res = atoi(s.c_str());
        return res <= 255 && res >= 0;
    }
};

不同点：

1、注意字符串的处理

s.substr(0, i)；s.substr(i)

2、关于num的处理，也并不是一定保证num不变的 ，如题即把Num每次减去一部分，更加便捷。

题131：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"

输出:

[

  ["aa","b"],

  ["a","a","b"]

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/palindrome-partitioning

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考：

我们将已经检测好的回文子串放到字符串数组out中，当s遍历完了之后，将out加入结果res中。那么在递归函数中我们必须要知道当前遍历到的位置，用变量start来表示，所以在递归函数中，如果start等于字符串s的长度，说明已经遍历完成，将out加入结果res中，并返回。否则就从start处开始遍历，由于不知道该如何切割，所以我们要遍历所有的切割情况，即一个字符，两个字符，三个字符，等等。。首先判断取出的子串是否是回文串，调用一个判定回文串的子函数即可，这个子函数传入了子串的起始和终止的范围，若子串是回文串，那么我们将其加入out，并且调用递归函数，此时start传入 i+1，之后还要恢复out的状态。

代码： 

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> out;
        helper(s, 0, out, res);
        return res;
    }
    void helper(string s, int start, vector<string>& out, vector<vector<string>>& res) {
        if (start == s.size()) { res.push_back(out); return; }
        for (int i = start; i < s.size(); ++i) {
            if (!isPalindrome(s, start, i)) continue;
            out.push_back(s.substr(start, i - start + 1));
            helper(s, i + 1, out, res);
            out.pop_back();
        }
    }
    bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) return false;
            ++start; --end;
        }
        return true;
    }
};

题目842

给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

形式上，斐波那契式序列是一个非负整数列表 F，且满足：

0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；

F.length >= 3；

对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 S 拆分出来的所有斐波那契式的序列块，如果不能拆分则返回 []。

示例 1：

输入："123456579"
输出：[123,456,579]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码 

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        vector<int> res, out;
        helper(S, 0, out, res);
        return res;
    }
    void helper(string& S, int start, vector<int>& out, vector<int>& res) {
        if (!res.empty()) return;
        if (start >= S.size() && out.size() >= 3) {
            res = out; return;
        }
        for (int i = start; i < S.size(); ++i) {
            string cur = S.substr(start, i - start + 1);
            if ((cur.size() > 1 && cur[0] == '0') || cur.size() > 10) break;
            long num = stol(cur), len = out.size();
            if (num > INT_MAX) break;
            if (out.size() >= 2 && num != (long)out[len - 1] + out[len - 2]) continue;
            out.push_back(num);
            helper(S, i + 1, out, res);
            out.pop_back();
        }
    }
};

思考

1、注意结果是整数形式，而不是字符串。因此需要把解转化为整形，我们从start位置起，每次取 i-start+1 长度的子串 cur，此时在转为int之前，需要先处理leading zeros的情况，判断若cur长度大于1，且首字符为0，直接break，还就是若cur的长度大于10，也break，为啥呢？因为整型的最大值是 2147483647，只有10位，所以当cur长度大于10时，一定会溢出。当cur长度为10时，也有可能溢出，这个在之后处理。好，现在将cur转为长整型 long，因为长度为10也可能溢出，所以要先转为长整型，然后在判断若大于整型最大值 INT_MAX，直接break。

2、注意解只要一个，我们用一个数组out来记录已经组成的序列，用结果res来保存结果。当out数组的个数大于等于3，并且已经遍历完了字符串S，那么此时就是可以把out数组中的内存赋值给结果res了，那么之后只要检测结果res不为空时，直接返回就可以了，这是个很好的剪枝操作，因为此题只需要一个正确答案即可

3、但从什么位置开始呢，每次都从头吗，这道题都数字不能重复使用，所以应该用个变量start来记录当前遍历到的位置，那么我们从start位置起，每次取 i-start+1 长度的子串 cur

4、out的前面的解，表示前面数据与准备待接入数据的关系，用

long num = stol(cur), len = out.size();

            if (num > INT_MAX) break;

            if (out.size() >= 2 && num != (long)out[len - 1] + out[len - 2]) continue;

同类题目：306

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1:

输入: "112358"

输出: true 

解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2:

输入: "199100199"

输出: true 

解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/additive-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码 

class Solution {
public:
    bool isAdditiveNumber(string num) {
        bool res = false;
        vector<long> out;
        helper(num, 0, out, res);
        return res;
    }
    void helper(string& num, int start, vector<long>& out, bool& res) {
        if (res) return;
        if (start >= num.size()) {
            if (out.size() >= 3) res = true; 
            return;
        }
        for (int i = start; i < num.size(); ++i) {
            string str = num.substr(start, i - start + 1);
            if ((str.size() > 1 && str[0] == '0') || str.size() > 19) break;
            long curNum = stol(str), n = out.size();
            if (out.size() >= 2 && curNum != out[n - 1] + out[n - 2]) continue;
            out.push_back(curNum);
            helper(num, i + 1, out, res);
            out.pop_back();
        }
    }
};

参考链接：

https://github.com/grandyang/leetcode/issues/131等一系列

leetcode 回溯算法 字符串
上一篇: 1208 尽可能使字符串相等
下一篇: 字符串大小写转换 -【C语言】

继续阅读