字符串类题目有两个基本技能：反转字符串和判断一个字符串是否是回文字符串

反转字符串

在 js 中可以直接调用相关 api 实现
主要是将字符串拆分成数组，然后利用数组的反转方法 reverse()，最后拼接成字符串

  1. const str = 'wangyi'
  2. const res = str.split('').reverse().join('')
  3. console.log(res) // iygnaw

验证回文字符串（LeetCode 125）

回文字符串，就是正着读和倒着读都一样的字符串，比如这样的：'yesey'
一个简单直观的判断方法就是：看这个字符串和它的反转字符串是不是相等

  1. function isPalindrome(str) {
  2.   // 先反转字符串
  3.   const reversedStr = str.split('').reverse().join('')
  4.   // 判断反转前后是否相等
  5.   return reversedStr === str
  6. }

但是回文字符串还有另一个特性：如果从中间位置“劈开”，那么两边的两个子串在内容上是完全对称的。因此我们也可以结合对称性来做判断，并且这是一个非常重要的特性：

  1. function isPalindrome(str){
  2.   const len = str.length
  3.   for(let i=0; i<len/2 ; i++ ){
  4.     // 判断前半部分和后半部分是否对称
  5.     if(str[i] !== str[len -1-i]){
  6.       return false
  7.     }
  8.   }
  9.   return true
  10. }

回文字符串衍生问题

真题描述：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串

示例:
输入：’aba’，输出：true
输入：’abca’，输出：true
思路分析：利用回文字符串的对称性和双指针来解

function validPalindrome(str){
  // 最多删除一个字符，判断是否是回文字符
  const len = str.length
  let i  = 0,j = len - 1
  // 当左右指针均满足对称时，一起向中间前进
  while( i < j && str[i]===str[j]){
    i++
    j--
  }
  // 工具函数，传左右边界
  function isPalindrome(left, right){ 
    while(left < right ){
      if(str[left] === str[right]){
        left--
        right++
      }else{
        return false
      }
    }
    return true
  }
  // 尝试判断跳过左指针元素后字符串是否回文
  if(isPalindrome(i+1, j)){
    return true
  }
  // 尝试判断跳过右指针元素后字符串是否回文
  if(isPalindrome(i, j-1)){
    return true
  }
  return false
}

字符串匹配——正则问题

设计一个支持以下两种操作的数据结构： void addWord(word) bool searchWord(word) search(word) 可以搜索文字或者正则表达式，字符串只包含字母a-z或者.， .表示任何一个字母

示例：
addWord(‘bad’)
addWord(‘dad’)
addWord(‘mad’)
search(‘pad’) —> false
search(‘bad’) —> true
search(‘.ad’) —> true
search(‘b..’) —> true
思路分析：
为了降低 search 查找时的复杂度，我们可以考虑以字符串的长度为 key，相同长度的字符串存在一个数组中，这样可以提高我们后续定位的效率。
由于 search() 的参数是字符串或者正则，所以需要判断并分别处理

// includes：判断数组或字符串是否包含
// some: 判断数组中至少有一个元素通过测试函数
function WordDictionary(){
  this.words = {}
}

WordDictionary.prototype.addWord = function(word){
  const len = word.length
  if(this.words[len]){
    this.words[len].push(word)
  }else{
    this.words[len] = [word]
  }
}

WordDictionary.prototype.searchWord = function(word){
  const len =  word.length
  if(!this.words[len]){
    return false
  }
  if(!word.includes('.')){
    return this.words[len].includes(word)
  }
  // 包含正则，需要先创建正则对象
  const reg = new RegExp(word)
  return this.words[len].some(item => reg.test(item))
}

const wordD = new WordDictionary()
wordD.addWord('bad')
wordD.addWord('dad')
console.log(wordD.searchWord('bad')) // true
console.log(wordD.searchWord('.d')) // false