leetcode_rust/problems/p000_0xx/
p000_005.rs

1//! # Description
2//! 
3//! Given a string `s`, return the longest palindromic substring in `s`.
4//! 
5//! | Example 1 |
6//! | :-- |
7//! | Input: s = "babad" |
8//! | Output: "bab" |
9//! 
10//! Explanation: "aba" is also a valid answer.
11//! 
12//! | Example 2 |
13//! | :-- |
14//! | Input: s = "cbbd" |
15//! | Output: "bb" |
16//!  
17//! Constraints:
18//! - `1 <= s.length <= 1000`
19//! - `s` consist of only digits and English letters.
20//! 
21//! Source: <https://leetcode.com/problems/longest-palindromic-substring/>
22
23////////////////////////////////////////////////////////////////////////////////
24
25/// Find longest palindrome of a given string.
26///
27/// It's possible to have multiple correct answer.
28/// See `tests/cases/c000_0xx/c000_005.rs` for more info.
29/// 
30/// # Arguments
31/// * `s` - original string to search.
32///
33/// # Examples
34/// ```
35/// use leetcode_rust::problems::p000_0xx::p000_005::longest_palindrome;
36/// let mut result_value = longest_palindrome(String::from("abbab"));
37/// assert_eq!(result_value, String::from("abba"));
38/// ```
39pub fn longest_palindrome(s: String) -> String {
40    by_array_index(&s).to_string()
41}
42
43#[cfg(test)]
44#[test]
45fn test_longest_palindrome() {
46    assert!(longest_palindrome(String::from("abbbabbbac")) == String::from("abbbabbba"));
47}
48
49#[allow(unused_assignments)]
50fn by_array_index(s: &str) -> &str {
51    let b = s.as_bytes();
52    if b.len() == 1 {
53        return s;
54    }
55
56    let mut cur_longest_start_idx = 0;
57    let mut cur_longest_end_idx = 0;
58    let mut ite = 1;
59    let mut cur_start_idx = 0;
60    let mut cur_end_idx = 0;
61    let mut should_repeat = false;
62    while ite <= b.len() - 1 || should_repeat {
63        cur_start_idx = ite - 1;
64        cur_end_idx = ite;
65        if should_repeat {
66            if ite < b.len() - 1 {
67                cur_end_idx = ite + 1;
68            }
69            ite += 1;
70        }
71        should_repeat = !should_repeat;
72        while cur_start_idx > 0 && cur_end_idx < b.len() - 1 && b[cur_end_idx] == b[cur_start_idx] {
73            cur_start_idx -= 1;
74            cur_end_idx += 1;
75        }
76        if b[cur_end_idx] != b[cur_start_idx]
77            && cur_end_idx - cur_start_idx > 2
78            && b[cur_end_idx - 1] == b[cur_start_idx + 1]
79        {
80            cur_end_idx -= 1;
81            cur_start_idx += 1;
82        } else if b[cur_end_idx] != b[cur_start_idx] {
83            continue;
84        }
85        if cur_end_idx - cur_start_idx > cur_longest_end_idx - cur_longest_start_idx {
86            cur_longest_end_idx = cur_end_idx;
87            cur_longest_start_idx = cur_start_idx;
88        }
89    }
90    &s[cur_longest_start_idx..(cur_longest_end_idx + 1)]
91}
92
93#[cfg(test)]
94#[test]
95fn test_by_array_index() {
96    assert!(by_array_index("QQ") == String::from("QQ"));
97    assert!(by_array_index("QAQ") == String::from("QAQ"));
98}
leetcode_rust/problems/p000_0xx/p000_005.rs

leetcode_rust/problems/p000_0xx/
p000_005.rs
