0214 - Shortest Palindrome

Description (leetcode)

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

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 * 10⁴
• s consists of lowercase English letters only.

submission

impl Solution {
    // best I can do O(n^2)
    pub fn shortest_palindrome(s: String) -> String {
        let rev_str = s.chars().rev().collect::<String>();
        for i in 0..rev_str.len() {
            if s.starts_with(&rev_str[i..]) {
                return format!("{}{}", &rev_str[..i], s);
            }
        }
        format!("{}{}", &rev_str, s)
    }
}