字符串算法
# 字符串算法
# 📋 学习目标
- 掌握字符串的基本操作
- 理解字符串匹配算法
- 学会字符串处理的常用技巧
- 熟练解决字符串相关问题
# 🔤 基础操作
# 字符串反转
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) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left)) !=
Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
# 🔍 字符串匹配
# KMP算法
public int[] computeLPS(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
public int kmpSearch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] lps = computeLPS(pattern);
int i = 0; // text的索引
int j = 0; // pattern的索引
while (i < n) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == m) {
return i - j; // 找到匹配
} else if (i < n && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1; // 未找到
}
# Rabin-Karp算法
public int rabinKarp(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int prime = 101;
int patternHash = 0;
int textHash = 0;
int h = 1;
// 计算h = pow(256, m-1) % prime
for (int i = 0; i < m - 1; i++) {
h = (h * 256) % prime;
}
// 计算模式串和文本第一个窗口的哈希值
for (int i = 0; i < m; i++) {
patternHash = (256 * patternHash + pattern.charAt(i)) % prime;
textHash = (256 * textHash + text.charAt(i)) % prime;
}
// 滑动窗口
for (int i = 0; i <= n - m; i++) {
if (patternHash == textHash) {
// 哈希值相等，检查字符是否真的匹配
boolean match = true;
for (int j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) {
match = false;
break;
}
}
if (match) {
return i;
}
}
// 计算下一个窗口的哈希值
if (i < n - m) {
textHash = (256 * (textHash - text.charAt(i) * h) +
text.charAt(i + m)) % prime;
if (textHash < 0) {
textHash += prime;
}
}
}
return -1;
}
# 🎯 经典问题
# 最长公共子序列
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
# 最长回文子串
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int start = 0, maxLen = 1;
for (int i = 0; i < s.length(); i++) {
// 奇数长度回文
int len1 = expandAroundCenter(s, i, i);
// 偶数长度回文
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() &&
s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}