Skip to content

Instantly share code, notes, and snippets.

@mchandschuh

mchandschuh/FindAllPalindromes.cs

Last active August 29, 2015 14:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mchandschuh/3f0bb998c7ff72c9d489 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mchandschuh/3f0bb998c7ff72c9d489 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. mchandschuh revised this gist Feb 19, 2015. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -111,7 +111,6 @@ private static bool IsPalindrome(string source)
    for (int i = 0; i < source.Length/2; i++)
    {
    // palindromes are mirrored, so keep comparing the ends until one doesn't match

    if (source[i] != source[source.Length - i - 1])
    {
    return false;
  2. mchandschuh revised this gist Feb 19, 2015. 1 changed file with 3 additions and 1 deletion.
    4 changes: 3 additions & 1 deletion FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -73,7 +73,9 @@ private static HashSet<string> FindAllUniquePalindromes_Described(string source)
    /// Searches the source string for all unique palindromes of any length
    /// </summary>
    /// <remarks>
    /// This is a better implementation after looking at the code
    /// This is a better implementation after looking at the code, and honestly, laid to to
    /// sleep and figured it a good idea to show a better way instead of just the way I initially
    /// described.
    /// </remarks>
    /// <param name="source">The source string to search</param>
    /// <returns>A list of all palindromes found in source</returns>
  3. mchandschuh revised this gist Feb 19, 2015. 1 changed file with 59 additions and 4 deletions.
    63 changes: 59 additions & 4 deletions FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -13,9 +13,12 @@ public void FindAllPalindromes()
    {
    const string source = "abcdcbaba";

    var palindromes = FindAllUniquePalindromes(source);

    foreach (var palindrome in palindromes)
    var palindromes_described = FindAllUniquePalindromes_Described(source);
    var palindromes_better = FindAllUniquePalindromes_Better(source);

    Assert.IsTrue(palindromes_described.SequenceEqual(palindromes_better));

    foreach (var palindrome in palindromes_described)
    {
    Console.WriteLine(palindrome);
    }
    @@ -37,9 +40,12 @@ public void FindAllPalindromes()
    /// <summary>
    /// Searches the source string for all unique palindromes of any length
    /// </summary>
    /// <remarks>
    /// This is the implementation described over the phone
    /// </remarks>
    /// <param name="source">The source string to search</param>
    /// <returns>A list of all palindromes found in source</returns>
    private static HashSet<string> FindAllUniquePalindromes(string source)
    private static HashSet<string> FindAllUniquePalindromes_Described(string source)
    {
    // result set
    var palindromes = new HashSet<string>();
    @@ -62,5 +68,54 @@ private static HashSet<string> FindAllUniquePalindromes(string source)
    }
    return palindromes;
    }

    /// <summary>
    /// Searches the source string for all unique palindromes of any length
    /// </summary>
    /// <remarks>
    /// This is a better implementation after looking at the code
    /// </remarks>
    /// <param name="source">The source string to search</param>
    /// <returns>A list of all palindromes found in source</returns>
    private static HashSet<string> FindAllUniquePalindromes_Better(string source)
    {
    // result set
    var palindromes = new HashSet<string>();

    // for each character in source construct each substring and then test for palindrome
    for (int i = 0; i < source.Length; i++)
    {
    for (int j = i; j < source.Length; j++)
    {
    string consider = source.Substring(i, j - i + 1);

    // determine if this is a palindrome
    if (IsPalindrome(consider))
    {
    palindromes.Add(consider);
    }
    }
    }
    return palindromes;
    }

    /// <summary>
    /// Determines if the specified string is a palindrome (mirrored)
    /// </summary>
    /// <param name="source">The source string to check</param>
    /// <returns>True if the string is a palindrome</returns>
    private static bool IsPalindrome(string source)
    {
    for (int i = 0; i < source.Length/2; i++)
    {
    // palindromes are mirrored, so keep comparing the ends until one doesn't match

    if (source[i] != source[source.Length - i - 1])
    {
    return false;
    }
    }
    return true;
    }
    }
    }
  4. mchandschuh revised this gist Feb 19, 2015. 1 changed file with 8 additions and 21 deletions.
    29 changes: 8 additions & 21 deletions FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -13,7 +13,7 @@ public void FindAllPalindromes()
    {
    const string source = "abcdcbaba";

    var palindromes = FindAllPalindromes(source);
    var palindromes = FindAllUniquePalindromes(source);

    foreach (var palindrome in palindromes)
    {
    @@ -39,41 +39,28 @@ public void FindAllPalindromes()
    /// </summary>
    /// <param name="source">The source string to search</param>
    /// <returns>A list of all palindromes found in source</returns>
    private static HashSet<string> FindAllPalindromes(string source)
    private static HashSet<string> FindAllUniquePalindromes(string source)
    {
    // result set
    var palindromes = new HashSet<string>();

    // create all our queues which will hold aggregated characters from each index in the source
    var queues = Enumerable.Range(0, source.Length).ToDictionary(x => x, x => new Queue<char>());
    // for each character in source construct each substring and then test for palindrome
    for (int i = 0; i < source.Length; i++)
    {
    var queue = new Queue<char>(source.Length - i);
    for (int j = i; j < source.Length; j++)
    {
    // add the next character to our set
    Queue<char> queue = queues[i];
    // add the next character to our consider set
    queue.Enqueue(source[j]);

    // create the string represented by our queue of characters and check for palindrome
    var item = new string(queue.ToArray());
    if (IsPalindrome(item))
    // determine if this is a palindrome
    if (queue.SequenceEqual(queue.Reverse()))
    {
    palindromes.Add(item);
    palindromes.Add(new string(queue.ToArray()));
    }
    }
    }
    return palindromes;
    }

    /// <summary>
    /// Determines if a string is a palindrome
    /// </summary>
    /// <param name="str">The input string</param>
    /// <returns>True if the input string is a palindrome (mirror image)</returns>
    private static bool IsPalindrome(string str)
    {
    // the performance here can be greatly improved
    return str.SequenceEqual(str.Reverse());
    }
    }
    }
  5. mchandschuh revised this gist Feb 19, 2015. 1 changed file with 4 additions and 9 deletions.
    13 changes: 4 additions & 9 deletions FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -44,19 +44,14 @@ private static HashSet<string> FindAllPalindromes(string source)
    // result set
    var palindromes = new HashSet<string>();

    // keyed by the index in the string
    var queues = new Dictionary<int, Queue<char>>();
    // create all our queues which will hold aggregated characters from each index in the source
    var queues = Enumerable.Range(0, source.Length).ToDictionary(x => x, x => new Queue<char>());
    for (int i = 0; i < source.Length; i++)
    {
    for (int j = i; j < source.Length; j++)
    {
    Queue<char> queue;
    if (!queues.TryGetValue(i, out queue))
    {
    queue = new Queue<char>();
    queues[i] = queue;
    }

    // add the next character to our set
    Queue<char> queue = queues[i];
    queue.Enqueue(source[j]);

    // create the string represented by our queue of characters and check for palindrome
  6. mchandschuh revised this gist Feb 19, 2015. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -59,6 +59,7 @@ private static HashSet<string> FindAllPalindromes(string source)

    queue.Enqueue(source[j]);

    // create the string represented by our queue of characters and check for palindrome
    var item = new string(queue.ToArray());
    if (IsPalindrome(item))
    {
  7. mchandschuh created this gist Feb 19, 2015.
    83 changes: 83 additions & 0 deletions FindAllPalindromes.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,83 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using NUnit.Framework;

    namespace Genetic.Tests
    {
    [TestFixture]
    public class PalindromeTests
    {
    [Test]
    public void FindAllPalindromes()
    {
    const string source = "abcdcbaba";

    var palindromes = FindAllPalindromes(source);

    foreach (var palindrome in palindromes)
    {
    Console.WriteLine(palindrome);
    }

    /*
    * Output:
    a
    abcdcba
    b
    bcdcb
    c
    cdc
    d
    bab
    aba
    */
    }

    /// <summary>
    /// Searches the source string for all unique palindromes of any length
    /// </summary>
    /// <param name="source">The source string to search</param>
    /// <returns>A list of all palindromes found in source</returns>
    private static HashSet<string> FindAllPalindromes(string source)
    {
    // result set
    var palindromes = new HashSet<string>();

    // keyed by the index in the string
    var queues = new Dictionary<int, Queue<char>>();
    for (int i = 0; i < source.Length; i++)
    {
    for (int j = i; j < source.Length; j++)
    {
    Queue<char> queue;
    if (!queues.TryGetValue(i, out queue))
    {
    queue = new Queue<char>();
    queues[i] = queue;
    }

    queue.Enqueue(source[j]);

    var item = new string(queue.ToArray());
    if (IsPalindrome(item))
    {
    palindromes.Add(item);
    }
    }
    }
    return palindromes;
    }

    /// <summary>
    /// Determines if a string is a palindrome
    /// </summary>
    /// <param name="str">The input string</param>
    /// <returns>True if the input string is a palindrome (mirror image)</returns>
    private static bool IsPalindrome(string str)
    {
    // the performance here can be greatly improved
    return str.SequenceEqual(str.Reverse());
    }
    }
    }