常见算法之字符串

简介

收集 字符串 相关的常见算法

字符串旋转

切片法

String rotateString(String s, int n) {
  int length = s.length;
  n = n % length; // 防止 n 大于字符串长度
  return s.substring(n) + s.substring(0, n);
}

void main() {
  String s = "abcdef";
  print(rotateString(s, 2)); // 输出 "cdefab"
}

双重拼接

String rotateString(String s, int n) {
  int length = s.length;
  n = n % length;
  String sDouble = s + s; // 双重拼接
  return sDouble.substring(n, n + length);
}

void main() {
  String s = "abcdef";
  print(rotateString(s, 2)); // 输出 "cdefab"
}

循环重组

String rotateString(String s, int n) {
  int length = s.length;
  n = n % length;
  List<String> rotated = List.generate(length, (i) => s[(i + n) % length]);
  return rotated.join();
}

void main() {
  String s = "abcdef";
  print(rotateString(s, 2)); // 输出 "cdefab"
}

队列

import 'dart:collection';

String rotateString(String s, int n) {
  Queue<String> queue = Queue.of(s.split(''));
  for (int i = 0; i < n; i++) {
    queue.addLast(queue.removeFirst()); // 左旋转
  }
  return queue.join();
}

void main() {
  String s = "abcdef";
  print(rotateString(s, 2)); // 输出 "cdefab"
}

字符串翻转

切分重连

String reverseString(String s) {
  return s.split('').reversed.join();
}

void main() {
  String s = "abcdef";
  print(reverseString(s)); // 输出 "fedcba"
}

倒序遍历

String reverseString(String s) {
  String reversed = '';
  for (int i = s.length - 1; i >= 0; i--) {
    reversed += s[i];
  }
  return reversed;
}

void main() {
  String s = "abcdef";
  print(reverseString(s)); // 输出 "fedcba"
}

双指针 *

String reverseString(String s) {
  List<String> chars = s.split('');
  int left = 0;
  int right = chars.length - 1;

  while (left < right) {
    // 交换左右字符
    String temp = chars[left];
    chars[left] = chars[right];
    chars[right] = temp;

    left++;
    right--;
  }

  return chars.join();
}

void main() {
  String s = "abcdef";
  print(reverseString(s)); // 输出 "fedcba"
}

递归翻转

String reverseString(String s) {
  if (s.isEmpty) {
    return s;
  }
  return reverseString(s.substring(1)) + s[0];
}

void main() {
  String s = "abcdef";
  print(reverseString(s)); // 输出 "fedcba"
}

最大回文字符串

中心扩散法 *

以每个字符和每两个字符之间的位置作为中心，向外扩展寻找回文子串

String longestPalindrome(String s) {
  if (s.isEmpty) return "";

  int start = 0, end = 0;

  for (int i = 0; i < s.length; i++) {
    int len1 = expandAroundCenter(s, i, i); // 奇数长度回文
    int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度回文
    int len = len1 > len2 ? len1 : len2;

    if (len > end - start) {
      start = i - (len - 1) ~/ 2;
      end = i + len ~/ 2;
    }
  }

  return s.substring(start, end + 1);
}

// 辅助函数：从中心向两侧扩展，返回回文的长度
int expandAroundCenter(String s, int left, int right) {
  while (left >= 0 && right < s.length && s[left] == s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

// 测试代码
void main() {
  String s = "cbabcad";
  print("Longest Palindromic Substring is: ${longestPalindrome(s)}");
}

动态规划法

通过记录子字符串的回文性，来逐步构建和寻找最大回文子串。这个方法适合那些需要更好可读性和较好性能的场景。

String longestPalindromeDP(String s) {
  int n = s.length;
  if (n < 2) return s;

  List<List<bool>> dp = List.generate(n, (_) => List.filled(n, false));
  int start = 0, maxLength = 1;

  // 单个字符一定是回文
  for (int i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // 检查长度为2的回文
  for (int i = 0; i < n - 1; i++) {
    if (s[i] == s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLength = 2;
    }
  }

  // 动态规划检查长度大于2的子串
  for (int len = 3; len <= n; len++) {
    for (int i = 0; i < n - len + 1; i++) {
      int j = i + len - 1;
      if (s[i] == s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLength = len;
      }
    }
  }

  return s.substring(start, start + maxLength);
}

// 测试代码
void main() {
  String s = "cbabcad";
  print("Longest Palindromic Substring is: ${longestPalindromeDP(s)}");
}

第一个只出现一次的字符

Hash 算法

String? firstUniqueCharacter(String s) {
  // 创建一个 Map 来存储字符的出现次数
  Map<String, int> charCount = {};
​
  // 统计每个字符的出现次数
  for (int i = 0; i < s.length; i++) {
    String char = s[i];
    charCount[char] = (charCount[char] ?? 0) + 1;
  }
​
  // 找到第一个只出现一次的字符
  for (int i = 0; i < s.length; i++) {
    String char = s[i];
    if (charCount[char] == 1) {
      return char; // 返回第一个只出现一次的字符
    }
  }
​
  return null; // 如果没有只出现一次的字符，返回 null
}
​
// 测试代码
void main() {
  String testString = "swiss";
  String? result = firstUniqueCharacter(testString);
  if (result != null) {
    print("第一个只出现一次的字符是: $result");
  } else {
    print("没有找到只出现一次的字符");
  }
}