214. Shortest Palindrome

August 17, 2019

Introduction

It is the good idea to show how to learn to solve a hard level algorithm. I believe that the learning process will help me to overcome difficulty in my daily job and help me to prepare more challenging programming task. I tried so many times to learn to solve 214 Shortest palindrome recently, more than three times I asked the algorithm in the mock interview as an interviewer.

Case study

I did write a post to share my understanding today. Here is the link.

It is so challenge to learn KMP algorithm and understand how to construct KMP table. I learned quickly by watching the video.

From 5:37 - 8:04, the explanation how to build longest prefix and suffix table is easy for me to follow,
a b c d a b c a
0 1 2 3 4 5 6 7
0 0 0 0 1 2 3 1 <- Lps Array (longest prefix suffix array)

I will add more explanation how to solve the problem later.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _214_shortest_palindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            RunKMPTableTestcase();
            var result = ShortestPalindrome("aacecaaa");
        }

        /// <summary>
        /// study video 
        /// https://www.youtube.com/watch?v=GTJr8OvyEVQ
        /// Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)
        /// 5:37 - 8:04
        /// </summary>
        public static void RunKMPTableTestcase()
        {
            // KMP table should be [0,0,0,0,1,2,3,1]
            var lps = ComputeLpsArray("abcdabca");
        }

        public static string ShortestPalindrome(string s)
        {
            var charArray = s.ToCharArray();
            Array.Reverse(charArray);
            int[] table = ComputeLpsArray(s + "." + new string(charArray));
            charArray = s.Substring(table[table.Length - 1]).ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray) + s;
        }

        /// <summary>
        /// study code 
        /// https://leetcode.com/problems/shortest-palindrome/discuss/350795/C-Solution-O(n)-using-%22longest-prefix-suffix-array%22-of-KMP
        /// longest prefix and suffix array
        /// Detail explanation - 
        /// study video 
        /// https://www.youtube.com/watch?v=GTJr8OvyEVQ
        /// Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)
        /// 5:37 - 8:04
        /// a b c d a b c a
        /// 0 1 2 3 4 5 6 7
        /// 0 0 0 0 1 2 3 1
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private static int[] ComputeLpsArray(string str)
        {
            var length = str.Length;

            // default is 0 
            var lps = new int[length];

            for (int i = 1; i < length; i++)
            {
                int j = lps[i - 1];
                 
                while ((j > 0) && (str[i] != str[j]))
                {
                    j = lps[j - 1];
                }

                lps[i] = str[i] == str[j] ? j + 1 : j;
            }

            return lps;
        }
    }
}