字符串在算法面试中,单独考察的机会并不多,同样倾向于和一些经典算法(后面会讲的)结合来体现区分度。步子不能跨太大,不然容易扯着x。本节我们照样是先解决只需要数据结构知识做基础就可以解决的字符串问题。
在讲题之前,我首先要给大家点拨两个字符串相关的“基本算法技能”。这两个技能偶尔也会单独命题,但整体来看在综合性题目中的考察频率较高,需要大家着重熟悉、反复练习和记忆,确保真正做题时万无一失。
# 基本算法技能
30 秒速记
JS字符串不可变,要「原地」改得先转数组,改完join('')- 先定义「字符」是什么:
length按UTF-16单元算,'😀'.length === 2 Array.from(str)按码点拆,能保住普通emoji;用户眼里的「一个字」要用Intl.Segmenter- 两头往中间比用双指针,统计频次用
Map,连续区间约束用滑动窗口 - 测试要覆盖空串、单字符、重复字符、超长输入,别只测英文
字符串题动手之前,先问清楚题目里的「一个字符」指的是什么。 只处理英文小写字母,按下标取就够了;但 JS 的 length 按 UTF-16 单元计数,'😀'.length 是 2,带 emoji 或组合音标的文本按下标切就会出乱码。Array.from 按码点拆能保住大部分 emoji,按用户看到的字切要用 Intl.Segmenter。口径定了再选工具:比首尾用双指针,数次数用 Map,找连续片段用滑动窗口。
字符串算法的第一步不是立刻写循环,而是定义“字符”和“相等”。只处理英文小写字母时,按索引读取通常足够;一旦输入包含 emoji、组合音标或多语言文本,就要区分 UTF-16 code unit、Unicode code point 与用户看到的字素簇。这个口径会直接决定长度、切分、反转和回文判断是否正确。
确定字符语义后,再根据访问模式选工具:两端向中间收缩用双指针,统计出现次数用 Map,连续区间约束用滑动窗口,复杂模式匹配则考虑状态机或动态规划。每个方案都要补空串、单字符、重复字符和超长输入,不能只验证 ASCII 样例。
面试官追问
追问 1昵称最多 10 个字符,'😀'.length 却是 2,前后端先统一什么?
统一「字符」的口径:UTF-16 单元、Unicode 码点,还是用户看到的字。length 是单元,Array.from(s).length 是码点,按视觉字数要用 Intl.Segmenter。三端用同一种,不然前端放行了后端又拦。
追问 2题目只说输入是英文小写字母,还有必要上 Intl.Segmenter 吗?
没必要。契约限定了字符集,按下标访问就是对的,写进入参校验和测试就行。一旦需求放开到任意文本,再重新选口径。
追问 3用 Intl.Segmenter 数用户看到的字数,怎么写?
[...new Intl.Segmenter('zh', { granularity: 'grapheme' }).segment(s)].length。像 '👨👩👧' 这种家庭 emoji,length 是 8,Array.from 是 5,Segmenter 才是 1。
追问 4从判断回文扩展成找最长无重复子串,双指针还能复用吗?
对撞指针不行,它只比首尾。这题要用滑动窗口:右边一直扩,遇到重复字符就把左边收到重复位置的后一位,Map 记每个字符最后出现的下标,O(n)。
追问 5统计一大段文本里每个字符出现次数,用对象还是 Map?
Map。对象键会和 __proto__、constructor 这些原型属性冲突,Map 没这问题,遍历还保持插入顺序。
# 反转字符串
30 秒速记
- 最常见写法:
str.split('').reverse().join(''),英文没问题 split('')按UTF-16单元拆,会把emoji的代理对拆坏;Array.from(str)或[...str]按码点拆- 组合音标、家庭
emoji这种「一个字多个码点」的,要Intl.Segmenter按字素拆 - 手写版:转数组 → 左右指针交换 →
join('') - 字符串不可变,时间
O(n)、空间也是O(n),做不到真正的O(1)
反转字符串一行就能写:split('').reverse().join(''),但它只对英文这类单字节字符靠谱。 split('') 按 UTF-16 单元拆,emoji 由两个单元组成,反转后顺序颠倒就成了乱码;换成 Array.from(str) 按码点拆就能保住。再进一步,é 写成 e 加组合重音、家庭 emoji 由多个码点拼起来的情况,Array.from 也会拆开,要用 Intl.Segmenter 按用户看到的字切。面试手写的话我会转数组再用左右指针交换,最后 join 一次。
原文的 split('').reverse() 对纯英文成立,但会把 emoji 的代理对拆开。若题目只要求按 Unicode code point 反转,可以这样写:
function reverseText(text) {
const chars = Array.from(text)
let left = 0
let right = chars.length - 1
while (left < right) {
;[chars[left], chars[right]] = [chars[right], chars[left]]
left += 1
right -= 1
}
return chars.join('')
}
console.log(reverseText('A😀B')) // B😀A
Array.from() 能保住单个 emoji,却不能保证组合字素。例如 e 加组合重音可能仍被拆开;面向用户文本时用 new Intl.Segmenter(locale, { granularity: 'grapheme' }) 分段。算法时间 O(n),字符数组和结果占 O(n) 空间。
在 JS 中,反转字符串我们直接调相关 API 即可,相信不少同学都能手到擒来:
// 定义被反转的字符串
const str = 'juejin'
// 定义反转后的字符串
const res = str.split('').reverse().join('')
console.log(res) // nijeuj
面试官追问
追问 1'A😀B'.split('').reverse().join('') 为什么出乱码?
😀 在 JS 里是两个 UTF-16 单元组成的代理对,split('') 把它拆成两半,反转后两半顺序颠倒,拼不回原来的字符。换成 Array.from('A😀B').reverse().join('') 得到 'B😀A'。
追问 2为什么不推荐在循环里 result = char + result 拼出反转结果?
每次拼接都会生成一个新字符串,虽然现代引擎对拼接有优化,但写法上不如转数组交换清楚。转数组、双指针交换、最后 join('') 一次,意图明确,也方便改成按码点处理。
追问 3产品要按用户看到的字反转,有 e 加组合重音,换成 Array.from 够吗?
不够,Array.from 按码点拆,e 和重音是两个码点,反转后重音会跑到别的字母上。要用 new Intl.Segmenter(locale, { granularity: 'grapheme' }) 分段后再反转。
追问 4面试官要求 O(1) 额外空间反转字符串,JS 能做到吗?
JS 字符串不可变,不能原地换位置,生成新字符串就是 O(n)。如果题目给的是字符数组(比如 LeetCode 344 那种),双指针交换就是 O(1) 额外空间。
追问 5少量多语言昵称反转后显示异常,怎么取证?
拿原始字符串,分别打 s.length、Array.from(s).length 和 Segmenter 分段后的个数,看三个数是不是一样。不一样就说明那段文本有代理对或组合字符,再看反转用的是哪种拆法。
(这段代码需要你非常熟悉,一些公司一面为了试水,有时会单独考这个操作)。
# 判断一个字符串是否是回文字符串
30 秒速记
- 回文 = 正着读倒着读一样,用左右指针比对称位置,第一处不同就
return false - 不用真的构造反转串,省一次复制,还能提前退出
- 「忽略大小写、空格、标点」不是默认规则,题目说了才做,单独写成预处理
é有预组合和e加重音两种写法,按需先normalize('NFC')- 空串和单字符一般算回文;循环条件
left < right,奇数长度中间那个不用比
判断回文我一般用左右指针,从两头往中间比,碰到第一对不一样的直接返回 false。 这比 split('').reverse().join('') === str 好在两点:不用多造一个反转后的字符串,而且不是回文的时候很可能第一步就退出了。要注意「忽略大小写和标点」不是回文本身的定义,题目要求了才做,我会写成一个单独的预处理函数,双指针只管比。带 Unicode 的文本还要考虑 é 这种两种编码写法的情况,先 normalize('NFC') 再比。
function isPalindrome(text) {
const chars = Array.from(text.normalize('NFC'))
let left = 0
let