前端小算法之字符串操作(一)

1、最长公共前缀

查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

输入：strs = [“flower”,”flow”,”flight”]

输出：”fl”

解析： 找到所有字符串的公共前缀，那我们可以以任意一个字符串str来做第一次对比得出的最长公共前缀。

然后以 str 为标准与后面的字符串对比。 对比后得出新的公共前缀 str1，然后 str = str1。 继续往后对比。

下面是代码：

var longestCommonPrefix = function(strs) {
  if (strs.length === 0) return ''
  let i = 0
  let str = strs[0]
  let index = 1
  while (index < strs.length) {
    while (str[i] === strs[index][i] && i < str.length) {
      i++
    }
    str = str.substring(0, i)
    i = 0
    index++
  }
  return str
}
复制代码

2、最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

回文子串：从前往后读 === 从后往前读

输入：s = “babad”

输出：”bab”

解释：”aba” 同样是符合题意的答案。

解析：

中心拓展法：

有兴趣的同学可以另外去看看动态规划、马拉车算法

以某点为中心，向两侧进行拓展，假如以a为原点，然后两边拓展是 bab 满足回文子串的规则，那就就继续往两边拓展。 如果 匹配的是 bac ，那么就没有必须继续往两边去拓展了，因为后面匹配出来的串也肯定不是回文子串。

还需要考虑的是：不一定回文子串是奇数的，还有可能是偶数的。所以还有一种可能是以两个原点然后往两边进行拓展。

时间复杂度：O(n^2) 其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n-1 个，每个回文中心最多会向外扩展 O(n) 次。

空间复杂度：O(1)。

下面是参考代码：

var longestPalindrome = function(s) {
  if (s.length <= 1) return s
  let start = 0
  let end = 0
  for (let i = 0; i < s.length; i++) {
    let len1 = judgeIs(s, i, i) // 奇数情况
    let len2 = judgeIs(s, i, i + 1) // 偶数情况
    let len = Math.max(len1, len2)
    if (len > end - start) {
      start = i - (len - 1) / 2
      end = i + len / 2
    }
  }
  return s.substring(Math.round(start), end + 1)
}

var judgeIs = function (s, left, right) {
  let L = left
  let R = right
  while (L >= 0 && R < s.length && s.charAt(L) === s.charAt(R)) {
    L--
    R++
  }
  return R - L - 1
}
复制代码

3、字符串匹配算法：KMP

Knuth–Morris–Pratt（KMP）算法是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n)。

参考链接：

leetcode-cn.com/leetbook/re…
www.zhihu.com/question/21…

要弄懂 KMP 算法，首先要理解其中一个很核心的东西：部分匹配表(Partial Match Table)。弄懂了PMT这个表，就大致能理解了。

PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

前缀： 字符串：abc的前缀是 {a, ab} 这个集合就是字符串abc的前缀集合

后缀： 字符串：abc的后缀是 {bc, a} 这个集合就是字符串abc的后缀集合

两个集合的交集：{a}, 那么最长元素就是a,长度就是 1

对于字符串“abababca”，它的PMT如下表所示:

然后我们将 value 这个数组往右移动一位，然后第一位补-1，就形成了 next 数组

下面是获取next 数组的代码参考：

var getNext = function (needle) {
    let i = 0
    let j = -1
    let next = []
    next[0] = -1
    while (i < needle.length) {
        if (j === -1 || needle[i] === needle[j]) {
            i++
            j++
            next[i] = j
        } else {
            j = next[j]
        }
    }
    return next
}
复制代码

总体的代码：

var strStr = function(haystack, needle) {
    if (needle === '') return 0
    let i = 0
    let j = 0
    let next = getNext(needle)
    while(i < haystack.length && j < needle.length) {
        if (j === -1 || haystack.charAt(i) === needle.charAt(j)) {
            if(j === needle.length - 1) return (i - needle.length + 1)
            i++
            j++
        } else {
            j = next[j]
        }
    }
    return -1
}
var getNext = function (needle) {
    let i = 0
    let j = -1
    let next = []
    next[0] = -1
    while (i < needle.length) {
        if (j === -1 || needle[i] === needle[j]) {
            i++
            j++
            next[i] = j
        } else {
            j = next[j]
        }
    }
    return next
}
复制代码

4、翻转字符串中的单词

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

输入：”Let’s take LeetCode contest”

输出：”s’teL ekat edoCteeL tsetnoc”

解析：

这题可以从头遍历，以空格为一个单词的边界来做翻转

也可以将这个字符串换成数组后，对单个成员就行翻转

下面是参考代码：

var reverseWords = function(s) {
    s = s.split(' ')
    s = s.map(i => {
        return i.split('').reverse().join('')
    })
    return s.join(' ')
}
复制代码