/* Given a set of strings, find the longest common prefix. 

​

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

​

​

Example 1:

​

Input: ["flower","flow","flight"]

Output: "fl"

​

*/

​

​

​

using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        string[] arr = {"bla_c3", "bla_c2",

                    "bla_c4", "bla_c1", "bla_c10", "bla_c12", "bla_cab", "bla_ca10", "bla_ca1" };

        Console.WriteLine("ORIGINAL");

        foreach(var s in arr) 

            Console.WriteLine("-- " + s);

​

        string lcp = arr[0];

        for(int p=1;p<arr.Length-1;p++){

            lcp = LCP(lcp,arr[p]);

        }

        Console.WriteLine("LCP is " + lcp);

        Console.WriteLine("ORDERED");

        var strings = arr.OrderBy(s => s, new CustomComparer());

        foreach(var s in strings) 

            Console.WriteLine("-- " + s);

    }

    public static string LCP(string str1, string str2){

        int lastIndex = 0 ;

        if (str1.Length < str2.Length && str2.StartsWith(str1)) return str1;

        if (str2.Length < str1.Length && str1.StartsWith(str2)) return str2;

        for(int i=0; i<=str1.Length-1 && i<=str2.Length-1; i++){

            if(str1[i]!=str2[i])

                break;

            else

                lastIndex++;

        }

        return str1.Substring(0, lastIndex);    

    }   

}

public class CustomComparer : IComparer<string>

    {

    private static string LCP(string str1, string str2){

        int lastIndex = 0 ;

        if (str1.Length < str2.Length && str2.StartsWith(str1)) return str1;

        if (str2.Length < str1.Length && str1.StartsWith(str2)) return str2;

        for(int i=0; i<=str1.Length-1 && i<=str2.Length-1; i++){

            if(str1[i]!=str2[i])

                break;

            else

                lastIndex++;

        }

        return str1.Substring(0, lastIndex);    

    }   

        public int Compare(string s1, string s2)

        {

            var lcp = LCP(s1, s2);

            s1 = s1.Substring(lcp.Length);

            s2 = s2.Substring(lcp.Length);

            if (string.IsNullOrEmpty(s1)) return -1;

            if (string.IsNullOrEmpty(s2)) return 1;

            int x, y;

            bool xInt, yInt;

            xInt = int.TryParse(s1, out x);

            yInt = int.TryParse(s2, out y);

            if (xInt && yInt)

                return x.CompareTo(y);

            if (xInt && !yInt)

            {

                if (this.SplitInt(s2, out y, out s2))

                {

                    return x.CompareTo(y);

                }

                else

                {

                    return -1;

                }

            }

            if (!xInt && yInt)

            {

                if (this.SplitInt(s1, out x, out s1))

                {

                    return y.CompareTo(x);

                }

                else

                {

                    return 1;

                }

            }

​

            return s1.CompareTo(s2);

        }

​

        private bool SplitInt(string sin, out int x, out string sout)

        {

            x = 0;

            sout = null;

            int i = -1;                

            bool isNumeric = false;

            var numbers = Enumerable.Range(0, 10).Select(it => it.ToString());

            var ie = sin.GetEnumerator();

            while (ie.MoveNext() && numbers.Contains(ie.Current.ToString()))

            {

                isNumeric |= true;

                ++i;

            }

​

            if (isNumeric)

            {

                sout = sin.Substring(i + 1);

                sin = sin.Substring(0, i + 1);

                int.TryParse(sin, out x);

            }

​

            return false;

        }

    }