Tech Qu: Find all palindromes in a string

Wikipedia: A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted).

 

First, we need to define the minimum length to qualify as a palindrome. We’ll call this minLength.

• First filter non-letters and convert everything to upper case.
• Create an array of characters.
• Walk all possible strings of sufficient length and determine it they are matches.
• We avoid using string function to obtain good performance and small memory size.
• No recursions or functions calls

 

Function

1. public static int Palindromes(string a, int minLength)
2. {
3.   int result = 0;
4.   var letters = a.ToUpper().ToCharArray();
5.   // remove spaces etc, leave only A-Z
6.   var filtered = new StringBuilder();
7.   foreach (var t in letters)
8.   {
9.     if (t >= 'A' && t <= 'Z')
10.     {
11.       filtered.Append(t);
12.     }
13.   }
14.   letters = filtered.ToString().ToCharArray();
15.  
16.   if (letters.Length < minLength)
17.   {
18.     return 0;
19.   }
20.   for (var palindromeLength = minLength; palindromeLength <= letters.Length; palindromeLength++)
21.   {
22.     for (var startat = 0; startat < letters.Length - palindromeLength+1; startat++)
23.     {
24.       bool isP = true;
25.       var sIndex = startat;
26.       var eIndex = startat + palindromeLength-1;
27.       while (sIndex < eIndex)
28.       {
29.         if (letters[sIndex] == letters[eIndex])
30.         {
31.           sIndex++;
32.           eIndex--;
33.         }
34.         else
35.         {
36.           isP = false;
37.           break;
38.         }
39.       }
40.       if (isP)
41.       {
42.         Console.WriteLine(filtered.ToString().Substring(startat, palindromeLength));
43.         result++;
44.       }
45.     }
46.   }
47.   return result;
48. }

The unit test is simple and uses one known palindrome and random letters.

Unit Test

1. string[] testcases = { "Able WaS I sAw ELBA!","ABCBA", "ABACADAEAF"};
2.       foreach(var test in testcases)
3.       {
4.         Console.WriteLine(string.Format("{0} --> {1}",test, Questions.Palindromes(test,3)));
5.       }

 

The test run allows us to confirm correct operation.