手帐 Blog

主题

23 · 字符串常考 ​

目标：会验证回文、最长公共前缀；能讲清 atoi 的边界处理思路。

为什么面试会考 ​

字符串 = 数组 + 字符规则。前端日常处理 URL、表单、展示文案，面试常考：

  • 双指针判断回文
  • 纵向扫描公共前缀
  • 模拟解析（atoi）看边界意识

零基础概念 ​

JS 字符串不可变：s[i] 可读；改内容通常转数组或拼新串。

常用：

js
s.toLowerCase()
s.trim()
/[a-z0-9]/i.test(ch)
s.slice(i, j)

JS 模板：双指针回文 ​

js
function isPalindromeRange(s, l, r) {
  while (l < r) {
    if (s[l] !== s[r]) return false
    l++
    r--
  }
  return true
}

精讲题 ​

LeetCode 125. 验证回文串 ​

只看字母和数字，忽略大小写。

js
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  let l = 0
  let r = s.length - 1
  const ok = (c) => /[a-z0-9]/i.test(c)
  while (l < r) {
    while (l < r && !ok(s[l])) l++
    while (l < r && !ok(s[r])) r--
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
}

LeetCode 14. 最长公共前缀 ​

以第一个串为基准，逐字符比；或两两缩短前缀。

js
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  if (!strs.length) return ''
  let prefix = strs[0]
  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1)
      if (!prefix) return ''
    }
  }
  return prefix
}

LeetCode 8. 字符串转换整数 (atoi) ​

步骤（面试口述比抠每种边界更重要）：

  1. 丢弃前导空格
  2. 读可选正负号
  3. 读连续数字，越界夹到 32 位整型范围
  4. 遇到非数字停止
js
/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function (s) {
  const INT_MAX = 2 ** 31 - 1
  const INT_MIN = -(2 ** 31)
  let i = 0
  const n = s.length
  while (i < n && s[i] === ' ') i++
  let sign = 1
  if (i < n && (s[i] === '+' || s[i] === '-')) {
    sign = s[i] === '-' ? -1 : 1
    i++
  }
  let num = 0
  while (i < n && s[i] >= '0' && s[i] <= '9') {
    const d = s[i].charCodeAt(0) - 48
    if (num > Math.floor((INT_MAX - d) / 10)) {
      return sign === 1 ? INT_MAX : INT_MIN
    }
    num = num * 10 + d
    i++
  }
  return sign * num
}

练习清单 ​

题提示
LeetCode 344. 反转字符串对撞双指针交换
LeetCode 541. 反转字符串 II按 2k 分段
LeetCode 28. 找出字符串中第一个匹配项的下标暴力或 KMP（面试暴力可过）
LeetCode 3. 无重复字符的最长子串回到滑窗（第 07 篇）
LeetCode 49. 字母异位词分组回到哈希（第 09 篇）

今日验收 ​

  • [ ] 125 双指针跳过非法字符
  • [ ] 14 能解释「不断缩短 prefix」
  • [ ] 8 能按四步口述，不要求一次写无 bug

若你以前见过 ​

正则能秒杀一些题，但面试更想看双指针与模拟；会正则当加分，别当唯一解。