No KMP; Simple, easy to understand C#


  • 0
    G
    1. Find the longest prefix which is a palindrome
    2. The remaining characters are the ones which need to be added to the beginning of the original string.
    public class Solution {
        public string ShortestPalindrome(string s) {
            int offset = LongestPalindromicPrefix(s);
            
            var builder = new StringBuilder();
            for (int i = s.Length - 1; i > offset; --i) {
                builder.Append(s[i]);
            }
            
            builder.Append(s);
            
            return builder.ToString();
        }
        
        // returns the end index of the longest palindromic prefix in s
        // e.g. abcde returns 0 ('a'); bcba returns 2 ('b')
        private int LongestPalindromicPrefix(string s) {
            
            int end = s.Length - 1;
            
            while (end >= 0) {
                
                if (IsPalindrome(s, 0, end)) {
                    return end;
                }
                
                --end;
            }
            
            return 0;
        }
        
        private bool IsPalindrome(string s, int begin, int end) {
            while (begin < end) {
                if (s[begin] != s[end]) {
                    return false;
                }
                
                ++begin;
                --end;
            }
            
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.