214. Shortest Palindrome

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

 

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

 

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of lowercase English letters only.

Rust Solution

struct Solution;
use std::iter::once;

impl Solution {
    fn shortest_palindrome(s: String) -> String {
        let n = s.len();
        let s_new: Vec<char> = s.chars().chain(once('#')).chain(s.chars().rev()).collect();
        let n_new = s_new.len();
        let mut f = vec![0; n_new];
        for i in 1..n_new {
            let mut t = f[i - 1];
            while t > 0 && s_new[i] != s_new[t] {
                t = f[t - 1];
            }
            if s_new[i] == s_new[t] {
                t += 1;
            }
            f[i] = t;
        }
        s.chars()
            .rev()
            .take(n - f.last().unwrap())
            .chain(s.chars())
            .collect()
    }
}

#[test]
fn test() {
    let s = "aacecaaa".to_string();
    let res = "aaacecaaa".to_string();
    assert_eq!(Solution::shortest_palindrome(s), res);
    let s = "abcd".to_string();
    let res = "dcbabcd".to_string();
    assert_eq!(Solution::shortest_palindrome(s), res);
}

Having problems with this solution? Click here to submit an issue on github.