字符串✅

字符串匹配

答案

核心概念 设计支持点号 . 通配符的词典查找结构（LeetCode 211）：

底层数据结构：采用字典树（Trie / 前缀树）。每个 Trie 节点包含子节点哈希表（或 26 叉数组）以及标记单词结尾的布尔值 isEnd。
添加单词 (addWord)：从根节点出发逐字符向下挂载，时间复杂度 $O(L)$（$L$ 为单词长度）。
查询单词 (search)：遇到普通字符走精确匹配；遇到通配符 . 时，使用 DFS 递归回溯尝试匹配当前节点的所有子节点。

代码实现：

class TrieNode {
  constructor () {
    this.children = {}
    this.isEnd = false
  }
}

class WordDictionary {
  constructor () {
    this.root = new TrieNode()
  }

  addWord (word) {
    let node = this.root
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode()
      }
      node = node.children[ch]
    }
    node.isEnd = true
  }

  search (word) {
    const dfs = (index, node) => {
      if (index === word.length) {
        return node.isEnd
      }

      const ch = word[index]
      if (ch === '.') {
        // 通配符匹配所有子节点
        for (const key of Object.keys(node.children)) {
          if (dfs(index + 1, node.children[key])) {
            return true
          }
        }
        return false
      } else {
        if (!node.children[ch]) {
          return false
        }
        return dfs(index + 1, node.children[ch])
      }
    }

    return dfs(0, this.root)
  }
}

// 验证
const dict = new WordDictionary()
dict.addWord('bad')
dict.addWord('dad')
dict.addWord('mad')
console.log(dict.search('pad')) // false
console.log(dict.search('bad')) // true
console.log(dict.search('.ad')) // true
console.log(dict.search('b..')) // true

面试官视角

考查前缀树数据结构的设计与 DFS 回溯剪枝能力。

字符串转换为整数

答案

核心概念 LeetCode 8（atoi）经典题目：模拟将字符串解析为 32 位有符号整数：

去除前导空格：丢弃开头的空白字符。
符号判定：检查首个非空字符是 + 还是 -，默认为正数。
数字提取与溢出防御：遇到非数字字符立即停止读取；累加过程中若超过 32 位有符号整型极值 $[−2^31, 2^31 − 1]$，直接 clamp 截断为 INT_MIN（$-2147483648$）或 INT_MAX（$2147483647$）。

代码实现：

function myAtoi (s) {
  const INT_MAX = 2147483647
  const INT_MIN = -2147483648

  let i = 0
  const n = s.length

  // 1. 去除前导空格
  while (i < n && s[i] === ' ') {
    i++
  }
  if (i >= n) return 0

  // 2. 判断符号
  let sign = 1
  if (s[i] === '+' || s[i] === '-') {
    sign = s[i] === '-' ? -1 : 1
    i++
  }

  // 3. 读取数字并处理 32 位越界
  let total = 0
  while (i < n && s[i] >= '0' && s[i] <= '9') {
    const digit = s.charCodeAt(i) - 48
    total = total * 10 + digit

    if (sign === 1 && total > INT_MAX) return INT_MAX
    if (sign === -1 && -total < INT_MIN) return INT_MIN

    i++
  }

  return sign * total
}

// 验证
console.log(myAtoi('42')) // 42
console.log(myAtoi('   -42')) // -42
console.log(myAtoi('4193 with words')) // 4193
console.log(myAtoi('-91283472332')) // -2147483648 (溢出截断)

面试官视角

考查对工程边界和数值溢出的严谨性测试，不借用外部黑盒函数（如 parseInt）考察状态机/手工遍历能力。

最长回文子串

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

const s = 'babad'

function longestPalindrome (s) {

}

答案

function longestPalindrome (s) {
  const n = s.length
  if (n < 2) return s
  let maxLen = 1; let start = 0
  const dp = Array.from({ length: n }, () => Array(n).fill(false))
  for (let i = 0; i < n; i++) dp[i][i] = true
  for (let j = 1; j < n; j++) {
    for (let i = 0; i < j; i++) {
      if (s[i] === s[j]) {
        if (j - i < 3) {
          dp[i][j] = true
        } else {
          dp[i][j] = dp[i + 1][j - 1]
        }
      }
      if (dp[i][j] && j - i + 1 > maxLen) {
        maxLen = j - i + 1
        start = i
      }
    }
  }
  return s.substring(start, start + maxLen)
}

module.exports = longestPalindrome

字符串的全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

const s = 'abc'

function permute (s) {

}

答案

function permute (s) {
  const results = []
  const used = Array(s.length).fill(false)
  function backtrack (path) {
    if (path.length === s.length) {
      results.push(path.join(''))
      return
    }
    for (let i = 0; i < s.length; i++) {
      if (used[i]) continue
      used[i] = true
      path.push(s[i])
      backtrack(path)
      path.pop()
      used[i] = false
    }
  }
  backtrack([])
  return results
}

module.exports = permute

字符串的子序列

给定一个字符串 s，返回所有可能的子序列。

const s = 'abc'

function subsequences (s) {

}

答案

function subsequences (s) {
  const results = []
  function backtrack (start, path) {
    results.push(path.join(''))
    for (let i = start; i < s.length; i++) {
      path.push(s[i])
      backtrack(i + 1, path)
      path.pop()
    }
  }
  backtrack(0, [])
  return results
}

module.exports = subsequences

无重复字符的最长子串

答案

核心概念 LeetCode 第 3 题经典算法：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度：

滑动窗口 + 哈希表（最优解）：维护左右双指针构成的滑动窗口 [start, end]，并用哈希表（Map）记录每个字符最后一次出现的索引。
窗口向右扩展（end 递增）。当遇到已出现过的字符时，若其上一次出现的索引在当前窗口内（lastIndex >= start），则将窗口左边界直接收缩跳跃到 lastIndex + 1，避免无效循环。
时间复杂度 $O(n)$，空间复杂度 $O(\min(m, n))$（字符集大小）。

代码实现：

function lengthOfLongestSubstring (s: string): number {
  const seen = new Map<string, number>()
  let start = 0
  let maxLength = 0

  for (let end = 0; end < s.length; end++) {
    const char = s[end]
    // 若字符在当前窗口内重复，收缩左边界
    if (seen.has(char) && seen.get(char)! >= start) {
      start = seen.get(char)! + 1
    }
    seen.set(char, end)
    maxLength = Math.max(maxLength, end - start + 1)
  }

  return maxLength
}

// 验证
console.log(lengthOfLongestSubstring('abcabcbb')) // 3 ("abc")
console.log(lengthOfLongestSubstring('bbbbb')) // 1 ("b")
console.log(lengthOfLongestSubstring('pwwkew')) // 3 ("wke")

面试官视角

考察点：双指针滑动窗口的基本功，能否敏锐处理 seen.get(char) >= start（防御已经滑出左边界的历史旧字符造成左边界倒退回弹）。

大数字符串相加/相乘

答案

核心概念 由于 JavaScript 的 Number 遵循 IEEE 754 双精度浮点数标准，安全整数范围为 $[-2^53 + 1, 2^53 - 1]$（即 Number.MAX_SAFE_INTEGER，约 16 位数字）。超过此范围直接计算会丢失精度。在没有或禁用 BigInt 时，需要使用字符串模拟竖式计算：

大数相加（LeetCode 415）：从两字符串末尾（最低位）向前遍历，按位相加并维护进位 carry，循环条件为 i >= 0 || j >= 0 || carry > 0。
大数相乘（LeetCode 43）：长度分别为 $M$ 和 $N$ 的两数相乘，结果最大长度不超过 $M + N$。初始化长度为 $M + N$ 的数组存储中间结果，num1[i] * num2[j] 的乘积落在索引 i + j 与 i + j + 1 上，最后从低位向高位统一进位处理。

代码实现：

// 1. 大数相加
function addStrings (num1, num2) {
  let i = num1.length - 1
  let j = num2.length - 1
  let carry = 0
  const res = []

  while (i >= 0 || j >= 0 || carry) {
    const n1 = i >= 0 ? num1.charCodeAt(i) - 48 : 0
    const n2 = j >= 0 ? num2.charCodeAt(j) - 48 : 0
    const sum = n1 + n2 + carry

    res.push(sum % 10)
    carry = Math.floor(sum / 10)
    i--
    j--
  }

  return res.reverse().join('')
}

// 2. 大数相乘
function multiplyStrings (num1, num2) {
  if (num1 === '0' || num2 === '0') return '0'

  const m = num1.length
  const n = num2.length
  const pos = new Array(m + n).fill(0)

  for (let i = m - 1; i >= 0; i--) {
    const n1 = num1.charCodeAt(i) - 48
    for (let j = n - 1; j >= 0; j--) {
      const n2 = num2.charCodeAt(j) - 48
      const mul = n1 * n2
      const p1 = i + j
      const p2 = i + j + 1

      const sum = mul + pos[p2]
      pos[p2] = sum % 10
      pos[p1] += Math.floor(sum / 10)
    }
  }

  // 去除前导 0
  let start = 0
  while (start < pos.length && pos[start] === 0) {
    start++
  }

  return pos.slice(start).join('')
}

// 验证
console.log(addStrings('99999999999999999999', '1')) // '100000000000000000000'
console.log(multiplyStrings('123', '456')) // '56088'

面试官视角

高频手写考察点！考察对进制进位边界、字符与数字转换细节以及乘法两层循环下标对应关系（i + j + 1 与 i + j）的掌握。

延伸阅读

字符串匹配​

字符串转换为整数​

最长回文子串​

字符串的全排列​

字符串的子序列​

无重复字符的最长子串​

大数字符串相加/相乘​

字符串匹配

字符串转换为整数

最长回文子串

字符串的全排列

字符串的子序列

无重复字符的最长子串

大数字符串相加/相乘