mkdocs/docs/android面试/算法与数据结构/字符串算法.md

字符串算法

目录

• 字符串基础
• 常见操作
• 字符串匹配
• 算法题
• 面试常见问题

---

字符串基础

字符串操作

// 1. 长度
String str = "Hello";
int len = str.length(); // 5

// 2. 查找
int index = str.indexOf("l"); // 2

// 3. 截取
String sub = str.substring(1, 3); // "el"

// 4. 替换
String newStr = str.replace("l", "L"); // "HeLLo"

---

常见操作

反转字符串

public String reverse(String s) {
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    while (left < right) {
        char temp = chars[left];
        chars[left] = chars[right];
        chars[right] = temp;
        left++;
        right--;
    }
    return new String(chars);
}

判断回文

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

---

字符串匹配

KMP 算法

// KMP：高效的字符串匹配算法
// 时间复杂度：O(n + m)

---

算法题

题1：最长公共前缀

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

---

面试常见问题

Q1: 字符串反转？

答案：

• 使用双指针
• 从两端向中间交换

Q2: 判断回文？

答案：

• 双指针比较
• 从两端向中间

---

最后更新：2024年