[第 4 期] 前端算法精选-字符串

[zzzzzzggggggg]

本期涉及到的算法技巧为字符串回溯算法，字符串相乘进位处理等等。

复原 IP 地址

LeetCode.93 ，难度中等

题目

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

示例:

输入: "25525511135"

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

思路

对于 IP 地址来说，要注意的点是，地址分为 4 段，每一段不能大于 255，且每一段如果开头是 0 的话那只能有一位。

考虑可以用回溯的思路，比如第一段可以在 2、25、255 里面选，当第一段是 2 的时候，第二段可以在 5、55、552 （超过 255 不符合要求）里选，第二段是 5 的时候，第三段可以在 5、52、525 （超过 255 不符合要求）里选，第三段是 5 的时候，第四段可以在 2、25、255 里选，其他情况可以以此类推。

代码如下：

/**
 * @param {string} s
 * @return {string[]}
 */
const restoreIpAddresses = function(s) {
    let res = [];
    backtrack(0, '', s, 4, res);
    
    return res;
};

/*
    pos：当前遍历到的位置
    ip：当前构造出的 ip
    s：字符串
    flag：当前是在处理第几段，ip 地址共 4 端
*/
const backtrack = function(pos, ip, s, flag, res) {
    if(flag < 0)
        return;
    
    if(pos === s.length && flag === 0) {
        res.push(ip.substring(0, ip.length-1));
        return;
    }
    
    for(let index = pos; index < pos+3;index++) {
        // 0 只能作为 IP 中的一段，不能出现 xx.01.xx.xx 这样的，所以 break
        if(index === pos && s[index] === '0') {
            backtrack(index + 1, ip + '0.', s, flag-1, res);
            break;
        }
        if(parseInt(s.substring(pos, index+1)) <= 255) {
            backtrack(index+1, ip + s.substring(pos, index+1) + '.', s, flag-1, res);
        }
    }
}

二进制求和

LeetCode.67 ，难度简单，常见于腾讯面试

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"

输出: "100"

示例 2:

输入: a = "1010", b = "1011"

输出: "10101"

思路

依然是个字符串按位相加的例子，不过要注意二进制的加法进位逻辑和两个字符串不一定会一样长。

代码如下：

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    if(a === "")
        return b;
    if(b === "")
        return a;
    
    let index1 = a.length-1;
    let index2 = b.length-1;
    let res = "";
    let carry = false;  // 进位
    
    while(index1 >= 0 && index2 >= 0) {
        let cur = "0";
        if(a[index1] === "1" && b[index2] === "1") {
            if(carry) {
                cur = "1";
            } else {
                cur ="0";
            }
            carry = true;
        } else if (a[index1] === "1" || b[index2] === "1") {
            if(carry) {
                cur = "0";
                carry = true;
            } else {
                cur = "1";
            }
        } else {
            if(carry) {
                cur = "1";
                carry = false;
            } else {
                cur = "0";
            }
        }
        index1--;
        index2--;
        res = cur + res;
    }
    
    let index = index1 >= 0 ? index1 : index2;
    let num = index1 >= 0 ? a : b;
    while(index >= 0) {
        let cur = "";
        if(num[index] === "1") {
            if(carry) {
                cur = "0";
                carry = true;
            } else {
                cur = "1";
                carry = false;
            }
        } else {
            cur = carry ? "1" : "0";
            carry = false;
        }
        index--;
        res = cur + res;
    }
    if(carry) {
        res = "1" + res;
    }
    return res;
};

感兴趣可关注我的公众号——前端亚古兽

[woodensail]

第二题哪儿这么麻烦，遍历一遍往数组塞不就行了。
function addBinary(a, b) {
const lenA = a.length, lenB = b.length;
const result = [0];
for (let i = 0; i < Math.max(lenA, lenB); i++) {
result[i] = result[i] + (a[lenA - i - 1] === '1' ? 1 : '') + (b[lenB - i - 1] === '1' ? 1 : '');
result.push(result[i] > 1 ? 1 : 0);
result[i] %= 2;
}
result.reverse();
return result.join('').replace(/^0+/g, '');
}

[woodensail]

我去，空格怎么都被干掉了

[mskf]

第一题个人认为在 backtrack 中反过来遍历效率会高一点
```
let index = pos; index < pos+3;index++
```
就是这边，从大到小遍历

[zzzzzzggggggg]

@woodensail
@mskf
哈哈，v 站的网友素质还是高的，稍等我晚上吃完饭看看你们的方法，感谢关注！

[purensong]

我寻思算法也分前后端嘛

[zzzzzzggggggg]

@purensong 不分，就是个名字而已嘛，老哥莫怪

[zzzzzzggggggg]

@mskf 我分析了一下，反过来效率还是一样的，依旧是一次一次的回溯😄

[zzzzzzggggggg]

@woodensail 试了下，你这个方法确实可以，我可以借鉴你的思路改造一下，就是把后面那两个 while 可以合入到第一个 while 的判断条件里面去

[mskf]

@zzzzzzggggggg 嗯，时间复杂度是一样的，我意思其实是 ip 地址三位数的多