leetcode_rust/problems_cn/p000_0xx/
p000_005.rs

1//! # 题目描述
2//! 
3//! 给你一个字符串 `s`，找到 `s` 中最长的回文子串。
4//! 
5//! 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
6//! 
7//! | 示例 1 | 
8//! | :-- |
9//! | 输入：s = "babad" |
10//! | 输出："bab" |
11//! 
12//! 解释："aba" 同样是符合题意的答案。
13//! 
14//! | 示例 2 |
15//! | :-- |
16//! | 输入：s = "cbbd" |
17//! | 输出："bb" |
18//! 
19//! 提示：
20//! - `1 <= s.length <= 1000`
21//! - `s` 仅由数字和英文字母组成
22//! 
23//! 来源：<https://leetcode.cn/problems/longest-palindromic-substring>
24
25////////////////////////////////////////////////////////////////////////////////
26
27/// 最长回文子串
28///
29/// 可能出现同一个字符串有多个最长回文子串的现象
30/// 参照 `tests/cases_cn/c000_0xx/c000_005.rs` 了解测试用例
31/// 
32///
33/// # 参数
34/// * `s` - 待搜索的原始字符串.
35///
36/// ```
37/// use leetcode_rust::problems_cn::p000_0xx::p000_005::longest_palindrome;
38/// let mut result_value = longest_palindrome(String::from("abbab"));
39/// assert_eq!(result_value, String::from("abba"));
40/// ```
41pub fn longest_palindrome(s: String) -> String {
42  by_array_index(&s).to_string()
43}
44
45#[cfg(test)]
46#[test]
47fn test_longest_palindrome() {
48  assert!(longest_palindrome(String::from("abbbabbbac")) == String::from("abbbabbba"));
49}
50
51#[allow(unused_assignments)]
52fn by_array_index(s: &str) -> &str {
53  let b = s.as_bytes();
54  if b.len() == 1 {
55      return s;
56  }
57
58  let mut cur_longest_start_idx = 0;
59  let mut cur_longest_end_idx = 0;
60  let mut ite = 1;
61  let mut cur_start_idx = 0;
62  let mut cur_end_idx = 0;
63  let mut should_repeat = false;
64  while ite <= b.len() - 1 || should_repeat {
65      cur_start_idx = ite - 1;
66      cur_end_idx = ite;
67      if should_repeat {
68          if ite < b.len() - 1 {
69              cur_end_idx = ite + 1;
70          }
71          ite += 1;
72      }
73      should_repeat = !should_repeat;
74      while cur_start_idx > 0 && cur_end_idx < b.len() - 1 && b[cur_end_idx] == b[cur_start_idx] {
75          cur_start_idx -= 1;
76          cur_end_idx += 1;
77      }
78      if b[cur_end_idx] != b[cur_start_idx]
79          && cur_end_idx - cur_start_idx > 2
80          && b[cur_end_idx - 1] == b[cur_start_idx + 1]
81      {
82          cur_end_idx -= 1;
83          cur_start_idx += 1;
84      } else if b[cur_end_idx] != b[cur_start_idx] {
85          continue;
86      }
87      if cur_end_idx - cur_start_idx > cur_longest_end_idx - cur_longest_start_idx {
88          cur_longest_end_idx = cur_end_idx;
89          cur_longest_start_idx = cur_start_idx;
90      }
91  }
92  &s[cur_longest_start_idx..(cur_longest_end_idx + 1)]
93}
94
95#[cfg(test)]
96#[test]
97fn test_by_array_index() {
98  assert!(by_array_index("QQ") == String::from("QQ"));
99  assert!(by_array_index("QAQ") == String::from("QAQ"));
100}
leetcode_rust/problems_cn/p000_0xx/p000_005.rs

leetcode_rust/problems_cn/p000_0xx/
p000_005.rs
