跳到主要内容

97 篇博文 含有标签「字符串」

查看所有标签

· 阅读需 4 分钟

1、题干​

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

 

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

 

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

2、解法1-逐行计算​

字符按 Z 字形排列后可以分割成多个竖列加斜列字符串，每串长度为 N = 2 * numRows - 2；可以按行计算结果字符串，不处于斜列上的字符其下标计算公式为 i + j * N，其中 i、j 分别为行列号，斜列上的字符下标计算公式为 j * N + N - i，逐行累加所有字符即可


3、代码​

var convert = function (s, numRows) {
    if (numRows === 1) return s;

    const N = 2 * numRows - 2;
    const col = Math.ceil(s.length / N);
    let res = '';
    for (let i = 0; i < numRows; i++) {
        for (let j = 0; j < col && i + j * N < s.length; j++) {
            if (i % (numRows - 1) === 0) res += s[i + j * N];
            else res += s[i + j * N] + (s[j * N + N - i] || '');
        }
    }

    return res;
};

4、执行结果​

image.png


5、解法2-矩阵填充​

3年前写的，实际是矩阵模拟的升级版本，思路是遍历字符串并计算当前字符所属行并追加到该行字符串末尾，最后累加所有行的字符串


6、代码​

var convert = function (s, numRows) {
    if (!s || numRows <= 1 || numRows >= s.length) return s;

    const matrix = new Array(numRows).fill('');
    const offset = 2 * numRows - 2 || 1;

    for (let i = 0; i < s.length; i++) {
        let mod = i % offset;
        if (mod >= numRows) mod = offset - mod;
        matrix[mod] += s[i];
    }

    return matrix.join('');
};

7、执行结果​

  • 执行用时: 132 ms
  • 内存消耗: 37.5 MB

· 阅读需 4 分钟

1、题干​

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

 

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

 

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

2、解法1-逐行计算​

字符按 Z 字形排列后可以分割成多个竖列加斜列字符串，每串长度为 N = 2 * numRows - 2；可以按行计算结果字符串，不处于斜列上的字符其下标计算公式为 i + j * N，其中 i、j 分别为行列号，斜列上的字符下标计算公式为 j * N + N - i，逐行累加所有字符即可


3、代码​

var convert = function (s, numRows) {
    if (numRows === 1) return s;

    const N = 2 * numRows - 2;
    const col = Math.ceil(s.length / N);
    let res = '';
    for (let i = 0; i < numRows; i++) {
        for (let j = 0; j < col && i + j * N < s.length; j++) {
            if (i % (numRows - 1) === 0) res += s[i + j * N];
            else res += s[i + j * N] + (s[j * N + N - i] || '');
        }
    }

    return res;
};

4、执行结果​

image.png


5、解法2-矩阵填充​

3年前写的，实际是矩阵模拟的升级版本，思路是遍历字符串并计算当前字符所属行并追加到该行字符串末尾，最后累加所有行的字符串


6、代码​

var convert = function (s, numRows) {
    if (!s || numRows <= 1 || numRows >= s.length) return s;

    const matrix = new Array(numRows).fill('');
    const offset = 2 * numRows - 2 || 1;

    for (let i = 0; i < s.length; i++) {
        let mod = i % offset;
        if (mod >= numRows) mod = offset - mod;
        matrix[mod] += s[i];
    }

    return matrix.join('');
};

7、执行结果​

  • 执行用时: 132 ms
  • 内存消耗: 37.5 MB

· 阅读需 2 分钟

1、题干​

复数 可以用字符串表示，遵循 "实部+虚部i" 的形式，并满足下述条件：

  • 实部 是一个整数，取值范围是 [-100, 100]
  • 虚部 也是一个整数，取值范围是 [-100, 100]
  • i2 == -1

给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。

 

示例 1：

输入：num1 = "1+1i", num2 = "1+1i"
输出："0+2i"
解释：(1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。

示例 2：

输入：num1 = "1+-1i", num2 = "1+-1i"
输出："0+-2i"
解释：(1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。

 

提示：

  • num1 和 num2 都是有效的复数表示。

2、解题思路​

使用正则表达式匹配出所有整数再进行计算

3、代码​

var complexNumberMultiply = function (num1, num2) {
    const [n1, n2, n3, n4] = (num1 + num2).match(/-?\d+/g).map((n) => +n);
    return `${n1 * n3 - n2 * n4}+${n1 * n4 + n2 * n3}i`;
};

4、执行结果​

image.png

· 阅读需 2 分钟

1、题干​

给你一个字符串 s ，根据下述规则反转字符串：

  • 所有非英文字母保留在原有位置。
  • 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

 

    示例 1：

    输入：s = "ab-cd"
    输出："dc-ba"

      示例 2：

      输入：s = "a-bC-dEf-ghIj"
      输出："j-Ih-gfE-dCba"

        示例 3：

        输入：s = "Test1ng-Leet=code-Q!"
        输出："Qedo1ct-eeLg=ntse-T!"

         

        提示

        • 1 <= s.length <= 100
        • s 仅由 ASCII 值在范围 [33, 122] 的字符组成
        • s 不含 '\"' 或 '\\'

        2、解题思路​

        双指针遍历字符串，左右都是字母时交换位置


        3、代码​

        var reverseOnlyLetters = function (s) {
            s = [...s];
            for (let l = 0, r = s.length - 1; l < r; l++, r--) {
                while (l < r && !(/[a-z]/i.test(s[l]))) l++;
                while (l < r && !(/[a-z]/i.test(s[r]))) r--;
                [s[l], s[r]] = [s[r], s[l]];
            }
            return s.join('');
        };

        4、执行结果​

        image.png

        · 阅读需 2 分钟

        1、题干​

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

         

        示例 1：

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

        示例 2：

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

         

        提示：

        • 1 <= n <= 8

        2、解题思路​

        总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。


        3、举个例子​

        • n=1时，组合情况仅一种：["()"]
        • n=2时
          • 遍历 n=1 的组合情况 ["()"]
          • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
          • 去重得到最终组合情况为：["()()","(())"]
        • n=3时
          • 遍历 n=2 的组合情况 ["()()","(())"]
          • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
          • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
          • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

        4、代码​

        var generateParenthesis = function (n) {
            let set = new Set(['()']);
            for (let c = 2; c <= n; c++) {
                let nextSet = new Set();
                for (const s of set) {
                    for (let j = 0; j <= s.length; j++) {
                        nextSet.add(s.slice(0, j) + '()' + s.slice(j));
                    }
                }
                set = nextSet;
            }
            return [...set];
        };

        5、执行结果​

        image.png

        · 阅读需 2 分钟

        1、题干​

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

         

        示例 1：

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

        示例 2：

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

         

        提示：

        • 1 <= n <= 8

         

        注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

        2、解题思路​

        总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。


        3、举个例子​

        • n=1时，组合情况仅一种：["()"]
        • n=2时
          • 遍历 n=1 的组合情况 ["()"]
          • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
          • 去重得到最终组合情况为：["()()","(())"]
        • n=3时
          • 遍历 n=2 的组合情况 ["()()","(())"]
          • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
          • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
          • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

        4、代码​

        var generateParenthesis = function (n) {
            let set = new Set(['()']);
            for (let c = 2; c <= n; c++) {
                let nextSet = new Set();
                for (const s of set) {
                    for (let j = 0; j <= s.length; j++) {
                        nextSet.add(s.slice(0, j) + '()' + s.slice(j));
                    }
                }
                set = nextSet;
            }
            return [...set];
        };

        5、执行结果​

        image.png

        · 阅读需 2 分钟

        1、题干​

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

         

        示例 1：

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

        示例 2：

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

         

        提示：

        • 1 <= n <= 8

         

        注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

        2、解题思路​

        总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。


        3、举个例子​

        • n=1时，组合情况仅一种：["()"]
        • n=2时
          • 遍历 n=1 的组合情况 ["()"]
          • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
          • 去重得到最终组合情况为：["()()","(())"]
        • n=3时
          • 遍历 n=2 的组合情况 ["()()","(())"]
          • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
          • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
          • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

        4、代码​

        var generateParenthesis = function (n) {
            let set = new Set(['()']);
            for (let c = 2; c <= n; c++) {
                let nextSet = new Set();
                for (const s of set) {
                    for (let j = 0; j <= s.length; j++) {
                        nextSet.add(s.slice(0, j) + '()' + s.slice(j));
                    }
                }
                set = nextSet;
            }
            return [...set];
        };

        5、执行结果​

        image.png

        · 阅读需 9 分钟

        1、题干​

        给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

        两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

        • s = s1 + s2 + ... + sn
        • t = t1 + t2 + ... + tm
        • |n - m| <= 1
        • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

        注意：a + b 意味着字符串 a 和 b 连接。

         

        示例 1：

        输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
        输出：true

        示例 2：

        输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
        输出：false

        示例 3：

        输入：s1 = "", s2 = "", s3 = ""
        输出：true

         

        提示：

        • 0 <= s1.length, s2.length <= 100
        • 0 <= s3.length <= 200
        • s1、s2、和 s3 都由小写英文字母组成

         

        进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

        要通过遍历解题需要用到3个指针，分别对应字符串 s1、s2、s3。官解说双指针不可行应该只考虑了 s1、s2 的指针且没有考虑指针重置的情况，实际只要指针可以重置就能求出正解，详情见解法2。


        2、解法1-回溯+记忆化​

        回溯过程可以理解为同时按字符串 s1、s2、s3 步进，若 s1 当前字符与 s3 当前字符相等则 s1 和 s3 的下标同时加1，若 s2 当前字符与 s3 当前字符相等则 s2 和 s3 的下标同时加1，若最终3个字符串能走到字符串末尾说明结果为 true。


        其中记忆化是将已访问过的路径使用哈希集合存储，若后续访问到已访问过的路径，则直接退出当前递归。


        3、代码​

        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            const visited = new Set();
            let res = false;
            function backtrace(i1, i2, i3) {
                if (i1 === s1.length && i2 === s2.length && i3 === s3.length) return res = true;
                if (visited.has(`${i1}-${i2}-${i3}`)) return false;
                visited.add(`${i1}-${i2}-${i3}`);

                if (s1[i1] === s3[i3]) backtrace(i1 + 1, i2, i3 + 1);
                if (s2[i2] === s3[i3]) backtrace(i1, i2 + 1, i3 + 1);
            }

            backtrace(0, 0, 0);

            return res;
        };

        4、执行结果​

        image.png


        5、解法2-三指针+模拟回溯+记忆化​

        本质上也是回溯+记忆化，只是使用三指针遍历模拟回溯过程，这是个非常规解法随便看看就好。


        三指针遍历模拟回溯的大体方案是：遍历 s3，若遇到 s1、s2 都可选的情况则选择 s1，并使用栈存储当前3个指针作为快照；若后续遍历无法继续下去且栈不为空则弹出栈顶快照，重置3个指针并选择 s2 继续遍历；若后续遍历无法继续且栈为空，则结果为 false。


        其中记忆化是将已访问过的路径使用哈希集合存储，若后续访问到已访问过的路径则看栈是否为空，栈为空则直接退出当前递归，栈不为空则弹出栈顶快照并重置指针。


        6、代码​

        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            let i1 = -1, i2 = -1, useStack = false;
            const stack = [], visited = new Set();

            for (let i = 0; i < s3.length; i++) {
                if (s1[i1 + 1] === s3[i] && s2[i2 + 1] === s3[i]) {
                    if (!useStack) stack.push([i, i1, i2]), i1 += 1;
                    else i2 += 1, useStack = false;
                }
                else if (s1[i1 + 1] === s3[i]) i1 += 1;
                else if (s2[i2 + 1] === s3[i]) i2 += 1;
                else {
                    if (!stack.length) return false;
                    [i, i1, i2] = stack.pop(), i -= 1, useStack = true;
                    continue;
                }

                if (visited.has(`${i}-${i1}-${i2}`)) {
                    if (!stack.length) return false;
                    [i, i1, i2] = stack.pop(), i -= 1, useStack = true;
                }
                else visited.add(`${i}-${i1}-${i2}`);
            }

            return true;
        };

        7、执行结果​

        • 执行用时: 72 ms
        • 内存消耗: 45.4 MB

        8、解法3-BFS+去重​

        这里使用非递归BFS解题，大体思路是：外层遍历字符串 s3，内层遍历当前可选择的所有 s1 和 s2 的下标组合，并且把下一层可选择的所有 s1 和 s2 的下标组合添加到下一层的队列中，如此遍历所有可行组合直至结束，若最终队列不为空则结果为 true。


        其中添加下标组合到队列中时一定要去重，否则会超时或内存溢出，去重可以使用双层 map 或者字符串哈希集合。


        9、代码​

        // BFS+双层map去重
        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            let choices = [[-1, -1]];
            for (let i = 0; i < s3.length; i++) {
                const nextChoices = [], map = {};
                for (const [i1, i2] of choices) {
                    if (s3[i] === s1[i1 + 1] && (!map[i1 + 1] || !map[i1 + 1][i2])) {
                        nextChoices.push([i1 + 1, i2]);
                        map[i1 + 1] ? (map[i1 + 1][i2] = 1) : (map[i1 + 1] = { [i2]: 1 });
                    }
                    if (s3[i] === s2[i2 + 1] && (!map[i1] || !map[i1][i2 + 1])) {
                        nextChoices.push([i1, i2 + 1]);
                        map[i1] ? (map[i1][i2 + 1] = 1) : (map[i1] = { [i2 + 1]: 1 });
                    }
                }
                choices = nextChoices;
            }

            return choices.length > 0;
        };

        // BFS+字符串哈希集合去重
        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            let choices = [[-1, -1]];
            for (let i = 0; i < s3.length; i++) {
                const nextChoices = [], set = new Set();
                for (const [i1, i2] of choices) {
                    if (s3[i] === s1[i1 + 1] && !set.has(`${i1 + 1},${i2}`)) {
                        nextChoices.push([i1 + 1, i2]);
                        set.add(`${i1 + 1},${i2}`);
                    }
                    if (s3[i] === s2[i2 + 1] && !set.has(`${i1},${i2 + 1}`)) {
                        nextChoices.push([i1, i2 + 1]);
                        set.add(`${i1},${i2 + 1}`);
                    }
                }
                choices = nextChoices;
            }

            return choices.length > 0;
        };

        10、执行结果​

        • 执行用时: 72 ms
        • 内存消耗: 48.3 MB

        11、解法4-动态规划​

        官解和其他优秀题解对于动态规划解法已经说得很清楚了，这里就贴下代码和执行结果


        12、代码​

        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            const dp = new Array(s1.length + 1).fill(0).map(() => new Array(s2.length + 1).fill(true));
            for (let i = 1; i < dp.length; i++) dp[i][0] = dp[i - 1][0] && s3[i - 1] === s1[i - 1];
            for (let j = 1; j < dp[0].length; j++) dp[0][j] = dp[0][j - 1] && s3[j - 1] === s2[j - 1];

            for (let i = 1; i < dp.length; i++) {
                for (let j = 1; j < dp[i].length; j++) {
                    dp[i][j] = (dp[i - 1][j] && s3[i + j - 1] === s1[i - 1]) || (dp[i][j - 1] && s3[i + j - 1] === s2[j - 1]);
                }
            }

            return dp[s1.length][s2.length];
        };

        13、执行结果​

        • 执行用时: 92 ms
        • 内存消耗: 47.7 MB

        · 阅读需 5 分钟

        1、题干​

        给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

        有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

        例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

         

        示例 1：

        输入：s = "25525511135"
        输出：["255.255.11.135","255.255.111.35"]

        示例 2：

        输入：s = "0000"
        输出：["0.0.0.0"]

        示例 3：

        输入：s = "1111"
        输出：["1.1.1.1"]

        示例 4：

        输入：s = "010010"
        输出：["0.10.0.10","0.100.1.0"]

        示例 5：

        输入：s = "10203040"
        输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

         

        提示：

        • 0 <= s.length <= 3000
        • s 仅由数字组成

         

        注意：本题与主站 93 题相同：https://leetcode-cn.com/problems/restore-ip-addresses/ 

        2、解法1-嵌套循环​

        三层嵌套循环确定 IP 地址的4个子串，并检验其合法性


        3、代码​

        var restoreIpAddresses = function (s) {
            const n = s.length;
            const valid = (str) => !((str.length > 1 && str[0] === '0') || +str > 255);

            const res = [];
            for (let i = 1; i < 4; i++) {
                if (n - i < 3 || n - i > 9) continue;
                for (let j = i + 1; j < i + 4; j++) {
                    if (n - j < 2 || n - j > 6) continue;
                    for (let k = j + 1; k < j + 4; k++) {
                        if (n - k < 1 || n - k > 3) continue;
                        const s1 = s.slice(0, i), s2 = s.slice(i, j);
                        const s3 = s.slice(j, k), s4 = s.slice(k);
                        if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
                    }
                }
            }

            return res;
        };

        代码中的校验可以简化，但遍历次数会增加

        var restoreIpAddresses = function (s) {
            const valid = (str) => !(str.length < 1 || str.length > 3 || (str.length > 1 && str[0] === '0') || +str > 255);

            const res = [];
            for (let i = 1; i < 4; i++) {
                for (let j = i + 1; j < i + 4; j++) {
                    for (let k = j + 1; k < j + 4; k++) {
                        const s1 = s.slice(0, i), s2 = s.slice(i, j);
                        const s3 = s.slice(j, k), s4 = s.slice(k);
                        if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
                    }
                }
            }

            return res;
        };

        4、执行结果​

        image.png


        5、解法2-回溯​

        使用回溯算法，在字符串 s 中选取3个索引作为选择路径（idxArr），其中索引值用于将字符串 s 分割成4个 IP 子串，以子串长度作为选择列表。

        注意

        • 选择列表（子串长度）只有 1、2、3 三种选择
        • 为了代码简洁性，每次递归都传入不同引用的选择路径（idxArr），这样可以省略撤销操作，但是消耗的内存会偏多

        6、代码​

        var restoreIpAddresses = function (s) {
            const n = s.length;
            const valid = (str) => !((str.length > 1 && str[0] === '0') || +str > 255);

            const res = [];
            function backtrace(idxArr) {
                const ln = idxArr.length, li = idxArr[ln - 1] || 0;

                if (n - li < 4 - ln || n - li > 3 * (4 - ln)) return;
                if (ln === 3) {
                    const s1 = s.slice(0, idxArr[0]), s2 = s.slice(idxArr[0], idxArr[1]);
                    const s3 = s.slice(idxArr[1], idxArr[2]), s4 = s.slice(idxArr[2]);
                    if (valid(s1) && valid(s2) && valid(s3) && valid(s4)) res.push(`${s1}.${s2}.${s3}.${s4}`);
                    return;
                }

                for (let i = 1; i <= 3; i++) backtrace([...idxArr, li + i]);
            }

            return backtrace([]), res;
        };

        7、执行结果​

        • 执行用时: 68 ms
        • 内存消耗: 43.4 MB

        · 阅读需 8 分钟

        1、题干​

        给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。

        两个字符串 s 和 t 交织 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

        • s = s1 + s2 + ... + sn
        • t = t1 + t2 + ... + tm
        • |n - m| <= 1
        • 交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

        提示：a + b 意味着字符串 a 和 b 连接。

         

        示例 1：

        输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
        输出：true

        示例 2：

        输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
        输出：false

        示例 3：

        输入：s1 = "", s2 = "", s3 = ""
        输出：true

         

        提示：

        • 0 <= s1.length, s2.length <= 100
        • 0 <= s3.length <= 200
        • s1、s2、和 s3 都由小写英文字母组成

         

        注意：本题与主站 97 题相同： https://leetcode-cn.com/problems/interleaving-string/

        遍历解题需要用到3个指针，分别对应字符串 s1、s2、s3。官解说双指针不可行应该只考虑了 s1、s2 的指针且没有考虑指针重置的情况，实际可以借助指针重置进行解题，详情见解法2。


        2、解法1-回溯+记忆化​

        回溯过程可以理解为同时按字符串 s1、s2、s3 步进，若 s1 当前字符与 s3 当前字符相等则 s1 和 s3 的下标同时加1，若 s2 当前字符与 s3 当前字符相等则 s2 和 s3 的下标同时加1，若最终3个字符串能走到字符串末尾说明结果为 true。


        其中记忆化是将已访问过的路径使用哈希集合存储，若后续访问到已访问过的路径，则直接退出当前递归。


        3、代码​

        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            const visited = new Set();
            let res = false;
            function backtrace(i1, i2, i3) {
                if (i1 === s1.length && i2 === s2.length && i3 === s3.length) return res = true;
                if (visited.has(`${i1}-${i2}-${i3}`)) return false;
                visited.add(`${i1}-${i2}-${i3}`);

                if (s1[i1] === s3[i3]) backtrace(i1 + 1, i2, i3 + 1);
                if (s2[i2] === s3[i3]) backtrace(i1, i2 + 1, i3 + 1);
            }

            backtrace(0, 0, 0);

            return res;
        };

        4、执行结果​

        image.png


        5、解法2-三指针+模拟回溯+记忆化​

        本质上也是回溯+记忆化，只是使用三指针遍历模拟回溯过程，这是个非常规解法随便看看就好。


        三指针遍历模拟回溯的大体方案是：遍历 s3，若遇到 s1、s2 都可选的情况则选择 s1，并使用栈存储当前3个指针作为快照；若后续遍历无法继续下去且栈不为空则弹出栈顶快照，重置3个指针并选择 s2 继续遍历；若后续遍历无法继续且栈为空，则结果为 false。


        其中记忆化是将已访问过的路径使用哈希集合存储，若后续访问到已访问过的路径则看栈是否为空，栈为空则直接退出当前递归，栈不为空则弹出栈顶快照并重置指针。


        6、代码​

        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            let i1 = -1, i2 = -1, useStack = false;
            const stack = [], visited = new Set();

            for (let i = 0; i < s3.length; i++) {
                if (s1[i1 + 1] === s3[i] && s2[i2 + 1] === s3[i]) {
                    if (!useStack) stack.push([i, i1, i2]), i1 += 1;
                    else i2 += 1, useStack = false;
                }
                else if (s1[i1 + 1] === s3[i]) i1 += 1;
                else if (s2[i2 + 1] === s3[i]) i2 += 1;
                else {
                    if (!stack.length) return false;
                    [i, i1, i2] = stack.pop(), i -= 1, useStack = true;
                    continue;
                }

                if (visited.has(`${i}-${i1}-${i2}`)) {
                    if (!stack.length) return false;
                    [i, i1, i2] = stack.pop(), i -= 1, useStack = true;
                }
                else visited.add(`${i}-${i1}-${i2}`);
            }

            return true;
        };

        7、执行结果​

        • 执行用时: 72 ms
        • 内存消耗: 45.4 MB

        8、解法3-BFS+去重​

        这里使用非递归BFS解题，大体思路是：外层遍历字符串 s3，内层遍历当前可选择的所有 s1 和 s2 的下标组合，并且把下一层可选择的所有 s1 和 s2 的下标组合添加到下一层的队列中，如此遍历所有可行组合直至结束，若最终队列不为空则结果为 true。


        其中添加下标组合到队列中时一定要去重，否则会超时或内存溢出，去重可以使用双层 map 或者字符串哈希集合。


        9、代码​

        // BFS+双层map去重
        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            let choices = [[-1, -1]];
            for (let i = 0; i < s3.length; i++) {
                const nextChoices = [], map = {};
                for (const [i1, i2] of choices) {
                    if (s3[i] === s1[i1 + 1] && (!map[i1 + 1] || !map[i1 + 1][i2])) {
                        nextChoices.push([i1 + 1, i2]);
                        map[i1 + 1] ? (map[i1 + 1][i2] = 1) : (map[i1 + 1] = { [i2]: 1 });
                    }
                    if (s3[i] === s2[i2 + 1] && (!map[i1] || !map[i1][i2 + 1])) {
                        nextChoices.push([i1, i2 + 1]);
                        map[i1] ? (map[i1][i2 + 1] = 1) : (map[i1] = { [i2 + 1]: 1 });
                    }
                }
                choices = nextChoices;
            }

            return choices.length > 0;
        };

        // BFS+字符串哈希集合去重
        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            let choices = [[-1, -1]];
            for (let i = 0; i < s3.length; i++) {
                const nextChoices = [], set = new Set();
                for (const [i1, i2] of choices) {
                    if (s3[i] === s1[i1 + 1] && !set.has(`${i1 + 1},${i2}`)) {
                        nextChoices.push([i1 + 1, i2]);
                        set.add(`${i1 + 1},${i2}`);
                    }
                    if (s3[i] === s2[i2 + 1] && !set.has(`${i1},${i2 + 1}`)) {
                        nextChoices.push([i1, i2 + 1]);
                        set.add(`${i1},${i2 + 1}`);
                    }
                }
                choices = nextChoices;
            }

            return choices.length > 0;
        };

        10、执行结果​

        • 执行用时: 72 ms
        • 内存消耗: 48.3 MB

        11、解法4-动态规划​

        官解和其他优秀题解对于动态规划解法已经说得很清楚了，这里就贴下代码和执行结果


        12、代码​

        var isInterleave = function (s1, s2, s3) {
            if (s1.length + s2.length !== s3.length) return false;

            const dp = new Array(s1.length + 1).fill(0).map(() => new Array(s2.length + 1).fill(true));
            for (let i = 1; i < dp.length; i++) dp[i][0] = dp[i - 1][0] && s3[i - 1] === s1[i - 1];
            for (let j = 1; j < dp[0].length; j++) dp[0][j] = dp[0][j - 1] && s3[j - 1] === s2[j - 1];

            for (let i = 1; i < dp.length; i++) {
                for (let j = 1; j < dp[i].length; j++) {
                    dp[i][j] = (dp[i - 1][j] && s3[i + j - 1] === s1[i - 1]) || (dp[i][j - 1] && s3[i + j - 1] === s2[j - 1]);
                }
            }

            return dp[s1.length][s2.length];
        };

        13、执行结果​

        • 执行用时: 92 ms
        • 内存消耗: 47.7 MB