Algorithm——String

发表于 分类于 ， 本文字数： 8k 阅读时长 ≈ 7 分钟

字符串

1. 反转字符串

344.编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

思路

使用双指针的方法，因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。

对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let r = s.length-1;
    for(let l = 0 ;l <= r ;l++ ){
        [s[l],s[r]] = [s[r],s[l]] 
        r--;
    }
    return s ;
};

2. 反转字符串II

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

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

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

思路

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function(s, k) {
    const n = s.length;
    const arr = Array.from(s);
    for (let i = 0; i < n; i += 2 * k) {
        reverse(arr, i, Math.min(i + k, n) - 1);
    }
    return arr.join('');
};

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

};

3. 替换空格

剑指05. 请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

思路

将字符串转换为数组，然后统计其中的空格数量。
根据空格数量和原有字符串有效字符长度，计算出刚好存放替换后的字符长度的数组。
创建两个指针，一个指数组末尾，一个指字符串有效位的末尾，实现原地修改。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    s = s.split("");
    let oldLen = s.length;
    let spaceCount = 0;
    for (let i = 0; i < oldLen; i++) {
        if (s[i] === ' ') spaceCount++;
    }
    s.length += spaceCount * 2;
    for (let i = oldLen - 1, j = s.length - 1; i >= 0; i--, j--) {
        if (s[i] !== ' ') s[j] = s[i];
        else {
            s[j - 2] = '%';
            s[j - 1] = '2';
            s[j] = '0';
            j -= 2;
        }
    }
    return s.join('');

};

4. 翻转字符串里的单词

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

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

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

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

1
2
输入：s = "the sky is blue"
输出："blue is sky the"
1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
1
2
3
4
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

思路

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @param {string} s
 * @return {string}
 */
 var reverseWords = function(s) {
   // 字符串转数组
   const strArr = Array.from(s);
   // 移除多余空格
   removeExtraSpaces(strArr);
   // 翻转
   reverse(strArr, 0, strArr.length - 1);

   let start = 0;

   for(let i = 0; i <= strArr.length; i++) {
     if (strArr[i] === ' ' || i === strArr.length) {
       // 翻转单词
       reverse(strArr, start, i - 1);
       start = i + 1;
     }
   }

   return strArr.join('');
};

// 删除多余空格
function removeExtraSpaces(strArr) {
  let slowIndex = 0;
  let fastIndex = 0;

  while(fastIndex < strArr.length) {
    // 移除开始位置和重复的空格
    if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
      fastIndex++;
    } else {
      strArr[slowIndex++] = strArr[fastIndex++];
    }
  }

  // 移除末尾空格
  strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
}

// 翻转从 start 到 end 的字符
function reverse(strArr, start, end) {
  let left = start;
  let right = end;

  while(left < right) {
    // 交换
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
    left++;
    right--;
  }
}
1
2
3
4
5
6
7
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};

5. 左旋转字符串

剑指58. 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"
1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

思路

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

最后就可以达到左旋n的目的，而不用定义新的字符串，完全在本串上操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} s
 * @param {number} n
 * @return {string}
 */
var reverseLeftWords = function (s, n) {
    /** Utils */
    function reverseWords(strArr, start, end) {
        let temp;
        while (start < end) {
            temp = strArr[start];
            strArr[start] = strArr[end];
            strArr[end] = temp;
            start++;
            end--;
        }
    }
    /** Main code */
    let strArr = s.split('');
    let length = strArr.length;
    reverseWords(strArr, 0, length - 1);
    reverseWords(strArr, 0, length - n - 1);
    reverseWords(strArr, length - n, length - 1);
    return strArr.join('');
};
1
2
3
4
5
6
const reverseLeftWords = (s, k) => {
    const len = s.length;
    const n = k % len;
    const double = `${s}${s}`;
    return double.slice(n, n + len);
};

6. 实现strStr()

  1. 找出字符串中第一个匹配项的下标，给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
    1
    2
    3
    4
    输入：haystack = "sadbutsad", needle = "sad"
    输出：0
    解释："sad" 在下标 0 和 6 处匹配。
    第一个匹配项的下标是 0 ，所以返回 0 。
    1
    2
    3
    输入：haystack = "leetcode", needle = "leeto"
    输出：-1
    解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

KMP

KMP有什么用

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

前缀表

next数组就是一个前缀表（prefix table）。

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

最长公共前后缀？

文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

因为前缀表要求的就是相同前后缀的长度。

而最长公共前后缀里面的“公共”，更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。

所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…..

前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力

如何计算前缀表

接下来就要说一说怎么计算前缀表。

如图：

KMP精讲5

长度为前1个字符的子串a，最长相同前后缀的长度为0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

KMP精讲6

长度为前2个字符的子串aa，最长相同前后缀的长度为1。

KMP精讲7

长度为前3个字符的子串aab，最长相同前后缀的长度为0。

以此类推： 长度为前4个字符的子串aaba，最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图： KMP精讲8

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀表与next数组

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

为什么这么做呢，其实这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

使用next数组来匹配

以下我们以前缀表统一减一之后的next数组来做演示。

有了next数组，就可以根据next数组来 匹配文本串s，和模式串t了。

注意next数组是新前缀表（旧前缀表统一减一了）。

KMP精讲4

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    let n = haystack.length
    let m = needle.length
    if(m === 0) return 0

    let next = new Array(m).fill(0)
    for(let i = 1, j = 0; i < m; i++){
        while(j > 0 && needle[i] !== needle[j]){
            j = next[j - 1]
        }
        if(needle[i] === needle[j]){
            j++
        }
        next[i] = j
    }

    // 搞懂上面的，下面的也就懂了
    for(let i = 0, j = 0; i < n; i++){
        // 如果当前i 和 j不一致，就回退到上一个相等的位置的下一个看看是否匹配
        // 会不断回退，0为回退到边界，当回退到0意味着要重新从头开始匹配
        while(j > 0 && haystack[i] !== needle[j]){
            j = next[j - 1]
        }
        if( haystack[i] === needle[j]){
            j++
        }
        // 当j 和 m的长度相等时，就说明存在
        if(j === m){
            return i - m + 1
        }
    }
    return -1
};

7.重复的子字符串

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

1
2
3
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
1
2
输入: s = "aba"
输出: false
1
2
3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

思路

为了避免这种无用的环绕，可以创建一个新的字符串str,它等于原来的字符串S再加上S自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么str = S + S = acdacd

acd移动的可能：dac、cda。其实都包含在了str中了。就像一个滑动窗口

一开始acd (acd) ，移动一次ac(dac)d,移动两次a(cda)cd。循环结束

所以可以直接判断str中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

代码

1
2
3
4
5
6
7
8
9
/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    let s1 = (s + s).slice(1, -1);
    return s1.indexOf(s) != -1;
};