LeetCode - 字符串

PS：按照代码随想录的题单顺序刷题，记录一下。

1. 反转字符串

描述

LeetCode344 - 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。简单

示例1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

思路

使用双指针，从头尾向中间移动，同时交换元素。

344 - 反转字符串

var reverseString = function(s) {
    let left = 0, right = s.length - 1;
    while(left < right) {
        let temp = s[right];
        s[right] = s[left];
        s[left] = temp;
        left++;
        right--;
    }
};

2. 反转字符串II

描述

LeetCode541 - 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。简单

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

思路

与上一题类似，按照题意使用双指针反转即可。将字符串转为数组，方便进行元素交换。

541 - 反转字符串II

var reverseStr = function(s, k) {
    const result = Array.from(s);
    for(let i = 0; i < s.length; i += 2*k) {
        reverse(result, i, Math.min(i + k, s.length) - 1);
    }
    return result.join('')
};

const reverse = (arr, left, right) => {
    while(left < right) {
        let temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
        left++;
        right--;
    }
}

3. 反转字符串里的单词

描述

LeetCode151 - 给你一个字符串 s，请你反转字符串中单词的顺序。中等

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例1：

输入：s = " the sky is blue"
输出："blue is sky the"

思路

首先去掉首尾空格，再从后往前遍历存入数组，需要注意中间多个空格的情况，最后翻转每个单词。

151 - 反转字符串里的单词

var reverseWords = function (s) {
    const result = [];
    const n = s.length;
    let left = 0, right = n - 1;
    // 去掉首尾空格
    while (s[left] == ' ') {
        left++;
    }
    while (s[right] == ' ') {
        right--;
    }
    // 从后往前遍历，存入数组
    while (left <= right) {
        // 过滤中间重复空格
        if(s[right] === ' ') {
            if (right > 0 && s[right - 1] == ' ') {
                right--;
                continue;
            }
        }
        result.push(s[right]);
        right--;
    }
    // 反转单词
    let start = 0;
    for(let i = 0; i < result.length; i++) {
        if(result[i] === ' ') {
            reverseStr(result, start, i - 1);
            start = i + 1;
        }
    }
    reverseStr(result, start, result.length - 1);
    return result.join('')
};

const reverseStr = (arr, left, right) => {
    while (left < right) {
        const temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
        left++;
        right--;
    }
}

4. 找出字符串中第一个匹配项的下标

描述

LeetCode28 - 给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。简单

示例1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

思路

在目标串中找子串出现的位置，模式匹配问题，应该熟悉 kmp 算法。

28 - 找出字符串中第一个匹配项的下标

const kmpNext = (patternStr) => {
  // 部分匹配表
  const next = new Array(patternArr.length);

  // 第一个位置最长公共前后缀长度肯定为0
  next[0] = 0;
  // 当前最长公共前后缀长度
  let len = 0;
  // 从第二个字符开始遍历，求每个子串的最长公共前后缀的长度
  let i = 1;
  while(i < patternStr.length) {
    // 已知上一子串[0, i-1]的最长公共前后缀的长度为len
    // 对应前缀字符串为[0, len-1]，记作prev，后缀字符串为[i-len, i-1]，记作next
    // 可知prev==next
    // 以上一子串的最长公共前后缀字符串作为参考，比较patternArr[len]和patternArr[i]
    if(patternStr[len] === patternStr[i]) {
      // 如果patternArr[len]和patternArr[i]，则当前最长公共前后缀长度可以加1
      next[i] = ++len;
      i++;
    } else {
      // 如果上一子串的最长公共前后缀长度为0，并且当前字符与第一个字符不相等
      // 则当前子串的最长公共前后缀长度肯定为0
      if(len === 0) {
        next[i] = 0;
        i++;
      } else {
        // 此时有prev==next，但是patternArr[len]!==patternArr[i]
        // 任一字符串的最长公共前缀字符串等于最长公共后缀字符串
        // 有prev的最长公共前缀字符串[0, next[len-1]-1]等于next的最长后缀字符串[i-next[len-1],i-1]
        // 因此可以比较patternArr[next[len-1]]和patternArr[i]
        len = next[len - 1]
      }
    }
    return next;
  }
}

const kmpSearch = (targetStr, patternStr) {
  // 首先计算部分匹配表
  const next = kmpNext(patternStr)
  let i = 0, j = 0;
  while(i < targetStr.length && j < patternStr.length) {
    // 相等时均右移
    if(targetStr[i] === patternStr[j]) {
      i++;
      j++;
    } else {
      if(j == 0) {
        // 模式串第一个字符都未匹配，直接将i后移
        i++;
      } else {
        // 此处思路类似于部分匹配表中不相等的思路
        // 不相等时，前面目标串和模式串已匹配部分肯定相等
        // 目标串中相等子串记作str1: [i-j,i-1]，模式串中子串记作str2: [0,j-1]
        // str1==str2，则str1的最长公共后缀字符串[i-next[j-1],i-1]等于str1的最长公共前缀字符串[0, next[j-1]-1]
        // 继续比较targetStr[i]与patternStr[next[j-1]]即可
        j = next[j - 1]
      }
    }
  }
  
  return j === patternStr.length ? i - j : -1;
}

5. 重复的子字符串

描述

LeetCode459 - 给定一个非空的字符串 s，检查是否可以通过由它的一个子串重复多次构成。简单

示例1:

输入：s = "abab"
输出：true
解释：可由子串 "ab" 重复两次构成。

示例2：

输入：s = "aba"
输出：false

思路

一开始想到符合条件的字符串，必定存在某一子串的最长公共前后缀字符串的长度等于子串长度的一半。因此可以通过部分匹配表进行剪枝。

另一方法是将目标字符串 S + S 进行拼接，然后去掉首尾字符，找该串中间是否有 S，出现则表明符合条件。

459 - 重复的子字符串

// 剪枝
var repeatedSubstringPattern = function (s) {
  // 计算部分匹配表
  const next = kmpNext(s);
  // 如果能由子串多次构成，部分匹配表中一定有个偶数索引，最长公共前后缀长度是子串长度的一半
  for (let i = 0; i < s.length; i++) {
    if (i % 2 !== 0 && next[i] === (i + 1) / 2 && s.length % next[i] === 0) {
      // 找到位置一半的子串，向后匹配
      let targetIndex = i + 1, patternIndex = 0;
      while (targetIndex < s.length) {
        if (s[targetIndex] === s[patternIndex]) {
          targetIndex++;
          patternIndex++;
        } else {
          break;
        }
        if (patternIndex > next[i] - 1) {
          patternIndex = 0;
        }
      }
      if (targetIndex === s.length && patternIndex === 0) return true;
    }
  }
  return false;
};

// kmp
var repeatedSubstringPattern = function(s) {
    const next = kmpNext(s);
    // 如果能由子串构成，则拼接后肯定能在中间找到s
    const target = s + s;

    let i = 1, j = 0;
    while(i < target.length && j < s.length) {
        if(target[i] === s[j]) {
            i++;
            j++;
        } else {
            if(j === 0) {
                i++;
            } else {
                j = next[j - 1];
            }
        }
    }
    return j === s.length && i !== s.length * 2;
};

// 部分匹配表
const kmpNext = (patternStr) => {
  const patternArr = Array.from(patternStr);
  const next = new Array(patternArr.length);

  next[0] = 0;
  let len = 0;

  let i = 1;
  while (i < patternArr.length) {
    if (patternArr[len] === patternArr[i]) {
      next[i] = ++len;
      i++;
    } else {
      if (len === 0) {
        next[i] = 0;
        i++;
      } else {
        len = next[len - 1];
      }
    }
  }

  return next;
}