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)
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;
}
}
}