[第 2 期] 前端算法精选-字符串系列

[zzzzzzggggggg]

今天精选的题目是关于字符串操作的，涉及到的技巧有字符串的滑动窗口思路、大数相乘。

字符串的排列

LeetCode.567 ，难度中等

题目

给定两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例 1:

输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").

示例 2:

输入: s1= "ab" s2 = "eidboaoo" 输出: False

注意：

1. 输入的字符串只包含小写字母
2. 两个字符串的长度都在 [1, 10,000] 之间

解法

理解一下题意，要求 s1 的字符串排列之一是第二个字符串的子串，比如 ab 是 eidbaooo 的子串，ba 也是 eidbaooo 的子串，同样的 baoo 也是 eidbaooo 的子串，所以这个规则可以抽象一下，如果 eidbaooo 里面存在一个子串，该子串的字符和 s1 的字符相同，且该子串字符出现的次数和 s1 中的字符出现次数相同，因此，可以考虑滑动窗口的思路。

首先维护一个 map1 来保存 s1 的字符以及每个字符出现的次数，再维护一个 map2 来保存当前窗口中的每个字符以及每个字符出现的次数，如果 map1 和 map2 相同，则说明滑动窗口中的字符子串和 s1 的排列之一相同，否则继续往右滑动。

1. 初始化，以 s1 长度为准，来构造两个 map，map1 = { a: 1, b: 1 }，map2 = { e: 1, i: 1 }。此时滑动窗口中的字符串是'ei'
2. 从 s2 的第 3 个（前两个已经被初始化过）字符'd'开始遍历，map1 和 map2 不同。此时窗口字符串是'ei'，删掉左边的'e'，更新 map2= { i: 1 }；加入第 3 个字符'd'，更新 map2 = { i: 1, d: 1 }
3. 此时遍历到第 4 个字符'b'，map1 和 map2 不同。此时窗口字符串是'id'，删掉左边的'i'，更新 map2={ d: 1 }；加入第 4 个字符串'b'，更新 map2={ d: 1, b: 1 }
4. 此时遍历到第 5 个字符'a'，map1 和 map2 不同。此时窗口的字符串是'db'，删掉左边的'd'，更新 map2={ b: 1 }；加入第 5 个字符串'a'，更新 map2={ b: 1, a: 1 }
5. 此时遍历到滴 6 个字符'o'，map1 和 map2 相同，返回 true

代码如下：

/\*\*
 \* @param {string} s1
 \* @param {string} s2
 \* @return {boolean}
 \*/
let checkMapEqual = function(m1, m2) { 
    let keys1 = Object.keys(m1), keys2 = Object.keys(m2);
    
    if(keys1.length !== keys2.length)
        return false;
    
    for(let i = 0;i < keys1.length;i++) {
        const curKey = keys1\[i\];
        if(m1\[curKey\] !== m2\[curKey\])
            return false;
    }
    
    return true;
}
let checkInclusion = function(s1, s2) {
    if(s1.length > s2.length)
      return false;
    
    let map1 = {}, map2 = {};
    const len1 = s1.length, len2 = s2.length;
    // 初始化 map
    for(let i = 0;i < len1;i++) {
        if(map1\[s1\[i\]\]) {
            map1\[s1\[i\]\]++
        } else {
            map1\[s1\[i\]\] = 1;
        }
        if(map2\[s2\[i\]\]) {
            map2\[s2\[i\]\]++
        } else {
            map2\[s2\[i\]\] = 1;
        }
    }
    for(let i = len1;i < len2;i++) {
        if(checkMapEqual(map1, map2)) {
            return true;
        }
        
        // 将窗口最左边的字符删去
        const leftChar = s2\[i-len1\];
        if(map2\[leftChar\] === 1) {
            delete map2\[leftChar\];
        } else {
            map2\[leftChar\]--;
        }
        // 在窗口右边加入一个字符
        const rightChar = s2\[i\];
        if(map2\[rightChar\]) {
            map2\[rightChar\]++;
        } else {
            map2\[rightChar\] = 1;
        }
    }
    return checkMapEqual(map1, map2);
};

字符串相乘

LeetCode.43 ，难度中等

题目

给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6"

示例 2:

输入: num1 = "123", num2 = "456" 输出: "56088"

说明：

1. num1和num2的长度小于 110。
2. num1和num2只包含数字0-9。
3. num1和num2均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger ）或直接将输入转换为整数来处理。

解法

先分析一下题目字符串相乘，要想模拟两个数字相乘，需要解决逐位相乘、再逐个相加的问题，过程中需要注意正确进位，比如'123'和'456'相乘：

1. 3 和 456 相乘，得到 1368 ；

2. 2 和 456 相乘，得到 912，因为 2 是十位，所以得到 9120 ；

3. 1 和 456 相乘，得到 456，因为 1 是百位，所以得到 45600 ；

4. 把 3 次乘积相加，加的过程中也要注意逐位相加，别忘了进位

代码如下：

/\*\*
 \* @param {string} num1
 \* @param {string} num2
 \* @return {string}
 \*/
const multiplyStep = (num1, pos, num2) => {
  let res = '';
  let carry = 0;
  for(let i = num2.length-1;i >= 0;i--) {
    const cur = num2\[i\];
    let product = parseInt(cur)\*num1;
    if(carry) {
      product += carry;
      carry = 0;
    }
    if(product >= 10) {
      carry = parseInt(product/10);
      product = product%10
    }
    res = product + res;
  }
  if(carry) {
    res = carry + res;
  }
  
  while(pos) {
    res += 0;
    pos--;
  }
  return res;
}
const addStep = (num1, num2) => {
  let len1 = num1.length;
  let len2 = num2.length;
  let num1Reversed = num1.split('').reverse().join('');
  let num2Reversed = num2.split('').reverse().join('');
  
  let index = 0;
  let res = '';
  let carry = false;
  while(index < len1 && index < len2) {
    const char1 = num1Reversed\[index\];
    const char2 = num2Reversed\[index\];
    
    let sum = parseInt(char1) + parseInt(char2);
    if(carry) {
      sum += 1;
      carry = false;
    }
    if(sum >= 10) {
      carry = true;
      sum = sum%10;
    }
    res += sum;
    index++;
  }
  while(index < len1) {
    let cur = num1Reversed\[index\];
    if(carry) {
      carry = false
      cur =  parseInt(cur)+1;
    }
    if(cur >= 10) {
      cur = cur%10;
      carry = true;
    }
    res += cur;
    index++;
  }
  while(index < len2) {
    let cur = num2Reversed\[index\];
    if(carry) {
      carry = false
      cur =  parseInt(cur)+1;
    }
    if(cur >= 10) {
      cur = cur%10;
      carry = true;
    }
    res += cur;
    index++;
  }
  if(carry) {
    res += 1;
    carry = false;
  }
  
  return res.split('').reverse().join('');
}
var multiply = function(num1, num2) {
  if(num1 === '0' || num2 === '0')
    return '0';
  
  let strArr = \[\];
  let res = '0';
  for(let i = num1.length-1;i >= 0;i--) {
    strArr.push(
      multiplyStep(num1\[i\], num1.length-1-i, num2)
    )
  }
    console.log(strArr);
  for(let i = 0;i < strArr.length;i++)  {
    res = addStep(res, strArr\[i\]);
  }
  
  return res;
};

---

感兴趣的可以关注我的微信公众号，前端亚古兽