汀的知识碎片

06 字符串整理：最长公共前缀、异位词与计数说

13 min read

字符串整理：最长公共前缀、异位词与计数说

摘要

本篇覆盖三道字符串经典题目：LeetCode 14（Longest Common Prefix）、LeetCode 49（Group Anagrams）和 LeetCode 38（Count and Say）。它们考察的方向各不相同：前缀对比、字符频率哈希、递推序列生成。难度相对较低，但各自有值得深挖的工程细节和优化技巧——最长公共前缀有纵向、横向、二分三种解法；异位词分组有排序键和质数哈希两种映射方式；Count and Say 是序列递推的最简单形式，也是理解”描述序列”这一类题目的基础。

第 1 章 LeetCode 14：最长公共前缀

1.1 题目

LeetCode 14 - Longest Common Prefix（简单）

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

输入: strs = ["flower","flow","flight"] → 输出: "fl"
输入: strs = ["dog","racecar","car"]    → 输出: ""（无公共前缀）
输入: strs = ["a"]                      → 输出: "a"
输入: strs = []                         → 输出: ""

1.2 解法一：横向扫描

将数组中的字符串两两取公共前缀，逐步缩短结果：

["flower","flow","flight"]
第一步: lcp("flower","flow") = "flow"
第二步: lcp("flow","flight") = "fl"
结果: "fl"

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        // 找 prefix 和 strs[i] 的公共前缀
        int j = 0;
        while (j < prefix.length() && j < strs[i].length() 
               && prefix.charAt(j) == strs[i].charAt(j)) {
            j++;
        }
        prefix = prefix.substring(0, j);
        if (prefix.isEmpty()) return ""; // 提前终止
    }
    return prefix;
}

复杂度：时间 （ 为所有字符串字符总数），空间 （不计输出）。

1.3 解法二：纵向扫描（推荐）

固定列索引 j，逐列检查所有字符串的第 j 个字符是否相同。第一个”不一致”列即为公共前缀长度：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    
    for (int j = 0; j < strs[0].length(); j++) {
        char c = strs[0].charAt(j);
        for (int i = 1; i < strs.length; i++) {
            // 越界或字符不等，前 j 个字符即为公共前缀
            if (j >= strs[i].length() || strs[i].charAt(j) != c) {
                return strs[0].substring(0, j);
            }
        }
    }
    return strs[0]; // strs[0] 本身就是公共前缀
}

直观理解：想象一个二维矩阵，行是字符串，列是字符位置，纵向扫描就是逐列检查。

复杂度：同样 ，但在公共前缀较短时能更快终止（不需要先构造 lcp 子串再比较）。

1.4 解法三：二分查找

公共前缀的长度在 0 到 minLen（最短字符串长度）之间，可以二分：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    
    int minLen = Integer.MAX_VALUE;
    for (String s : strs) minLen = Math.min(minLen, s.length());
    
    int lo = 0, hi = minLen;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2; // 上取整，防止死循环
        if (isCommonPrefix(strs, mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return strs[0].substring(0, lo);
}
 
private boolean isCommonPrefix(String[] strs, int len) {
    String prefix = strs[0].substring(0, len);
    for (int i = 1; i < strs.length; i++) {
        if (!strs[i].startsWith(prefix)) return false;
    }
    return true;
}

复杂度：时间 （ 为最短字符串长度），通常比纵向扫描慢，但二分本身是一种好的思维训练。

1.5 边界案例

  • 空数组：直接返回 ""
  • 数组中有空字符串：公共前缀长度为 0，返回 ""（纵向扫描的 j >= strs[i].length() 条件会处理这一情况）
  • 只有一个字符串：直接返回该字符串（纵向扫描 for 循环不执行，返回 strs[0]）

纵向扫描为何推荐

纵向扫描相对横向扫描的优势在于不需要分配中间字符串（strs[0].substring(0, j) 只在最终结果时才分配一次），而横向扫描每次都可能调用 substring 创建新对象。在高频调用的场景下差异显著。

第 2 章 LeetCode 49：字母异位词分组

2.1 题目

LeetCode 49 - Group Anagrams（中等）

给你一个字符串数组，请你将字母异位词组合在一起。字母异位词是由重新排列源单词的所有字母得到的一个新单词，所有输入均为小写字母。

输入: strs = ["eat","tea","tan","ate","nat","bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

2.2 核心思路：找”异位词标识符”

两个字符串互为异位词，当且仅当它们包含的字符集合（含频率）完全相同。因此，关键是找到一个函数 ，使得互为异位词的字符串映射到同一个 key，不是异位词的映射到不同 key。

2.3 解法一：排序键（最常用）

将每个字符串的字符排序后，作为 HashMap 的 key：

"eat" → 排序 → "aet"
"tea" → 排序 → "aet"  （同一组）
"tan" → 排序 → "ant"
"nat" → 排序 → "ant"  （同一组）
"bat" → 排序 → "abt"

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    
    return new ArrayList<>(map.values());
}

复杂度：时间 （ 个字符串，每个长度 ），空间 。

computeIfAbsent 是 Java 8 的 Map 方法，等价于：

if (!map.containsKey(key)) map.put(key, new ArrayList<>());
map.get(key).add(s);

2.4 解法二：字符频率键

不排序，而是将 26 个字母的出现频率编码成字符串 key：

"eat" → [1,0,0,0,1,0,...,1,...] → "1#0#0#0#1#0#...#1#..."

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    
    for (String s : strs) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        
        // 将频率数组编码为字符串 key（用 # 分隔避免歧义）
        StringBuilder sb = new StringBuilder();
        for (int freq : count) {
            sb.append(freq).append('#');
        }
        String key = sb.toString();
        
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    
    return new ArrayList<>(map.values());
}

复杂度：时间 ，空间 。相比排序键，时间从 降到 。

频率编码时为何用 # 分隔？

不加分隔符，[1,12] 和 [11,2] 都会编码成 "112"，导致不同异位词组被合并。用 # 分隔：[1,12] → "1#12#"，[11,2] → "11#2#"，两者不同。

2.5 解法三：质数哈希（趣味解法）

将 26 个字母映射到 26 个质数（a=2, b=3, c=5, ...），用所有字符对应质数的乘积作为 key。因为质数分解唯一，互为异位词的字符串乘积相同：

"eat": 2*5*29 = 290（a=2, e=5... 具体映射自定义）
"tea": 29*5*2 = 290  （乘法交换律，相同）
"tan": 29*2*13 = 754

private static final long[] PRIMES = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
    53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101
};
 
public List<List<String>> groupAnagrams(String[] strs) {
    Map<Long, List<String>> map = new HashMap<>();
    
    for (String s : strs) {
        long key = 1L;
        for (char c : s.toCharArray()) key *= PRIMES[c - 'a'];
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    
    return new ArrayList<>(map.values());
}

质数哈希的局限性

当字符串很长或字符频率很高时，乘积会溢出 long，导致哈希冲突。生产环境不建议用，但面试中作为一个”额外思路”是加分项。

第 3 章 LeetCode 38：Count and Say

3.1 题目

LeetCode 38 - Count and Say（中等）

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述：

countAndSay(1) = "1"
countAndSay(2) = "11"       （对 "1" 的描述：1个1，即"one 1"→"11"）
countAndSay(3) = "21"       （对 "11" 的描述：2个1→"21"）
countAndSay(4) = "1211"     （对 "21" 的描述：1个2,1个1→"1211"）
countAndSay(5) = "111221"   （对 "1211" 的描述：1个1,1个2,2个1→"111221"）

规则：对当前字符串，从左到右统计连续相同字符的个数，输出”个数+字符”，拼接得到下一个字符串。

3.2 实现

public String countAndSay(int n) {
    String result = "1";
    for (int i = 1; i < n; i++) {
        result = next(result);
    }
    return result;
}
 
private String next(String s) {
    StringBuilder sb = new StringBuilder();
    int len = s.length();
    int idx = 0;
    
    while (idx < len) {
        char c = s.charAt(idx);
        int count = 0;
        
        // 统计连续相同字符数
        while (idx < len && s.charAt(idx) == c) {
            idx++;
            count++;
        }
        
        sb.append(count).append(c);
    }
    
    return sb.toString();
}

手动验证（从 “1211” 生成 “111221”）：

idx=0: c='1', count=1 → "11"... 等等：
  s = "1211"
  idx=0: c='1', s[0]='1'==c, count=1, idx=1
         s[1]='2'!='1', 退出
         → append "11" ... 不对，应该 append count=1, c='1' → "11"?
  
  重读题目：count=1, c='1' → append "1" + "1" → "11"
  idx=1: c='2', s[1]='2'==c, count=1, idx=2
         s[2]='1'!='2', 退出
         → append "1" + "2" → "12"
  idx=2: c='1', s[2]='1'==c, count=1, idx=3
         s[3]='1'==c, count=2, idx=4
         越界，退出
         → append "2" + "1" → "21"
  
  结果: "11" + "12" + "21" = "111221" ✓

复杂度：每次迭代字符串长度最多增加两倍（不会无限增长，实际上接近 上限），第 次的字符串长度为 ，但对于题目给定的 ，完全可以接受。

3.3 用正则实现（简洁但非最优）

Java 正则可以用 (.)\1* 匹配连续相同字符：

public String countAndSay(int n) {
    String result = "1";
    for (int i = 1; i < n; i++) {
        Matcher m = Pattern.compile("(.)\\1*").matcher(result);
        StringBuilder sb = new StringBuilder();
        while (m.find()) {
            sb.append(m.group().length()).append(m.group().charAt(0));
        }
        result = sb.toString();
    }
    return result;
}

(.)\\1*：(.) 捕获一个字符，\\1* 匹配与第一个捕获组相同的字符 0 次或多次。m.group() 返回整个匹配串，长度即为 count。

这是字符串模拟的典型题

Count and Say 本身难度不高，但它是”游程编码”（Run-Length Encoding，RLE）的极简版本。RLE 是 BMP、TIFF 等图像格式的基础压缩算法，也在 DNA 序列分析中有广泛应用。

第 4 章 三道题的总结与对比

题目核心技术时间复杂度关键点
LeetCode 14纵向扫描 / 横向扫描尽早终止，纵向扫描更优
LeetCode 49哈希表 + 排序键/频率键 / 频率编码的分隔符不能省略
LeetCode 38字符串模拟（双指针）双指针统计连续相同字符

这三道题有一个共同点：都是字符串预处理的典型题。实际工程中，字符串预处理（归一化、分组、编码）是数据管道的重要步骤，这些题目所用的技术与生产代码高度重合。

下一篇预告

07 字符串模拟：Valid Number、整数与罗马互转 将进入字符串解析的复杂场景。LeetCode 65（Valid Number）是公认的最难解析题，需要用有限状态机（FSM）处理整数、浮点数、科学计数法的所有合法格式；LeetCode 12/13（Integer to Roman / Roman to Integer）则用贪心和哈希表简洁处理罗马数字的编解码规则。

Backlinks