[Longest] Longest Common Prefix

1. Example
INSTEAD OF USING A SUBTRING TO MATCH USE INDEX
str[0] as a basis and use append to avoid confusion over using subtring index

s= { "MAU", "MAKAN", "MALAM"}
there are two common prefixes of MAU, which are: "M" and "MA"
Among these, the Longest Common Prefix is "MA" which has a length of 2


2. Implementation
Q1: start from the first word, substring(0,i)i=1~ len
A1; compare it with the rest of string same length,
E.g., M len =1, check i=1 with M and M
MA len =2, check i =2 with MA and MA
MAU len =3, check i=3 wiht MAK and MAL => false
O(string len*array length)


Runtime Error Message:Line 62: java.lang.StringIndexOutOfBoundsException: String index out of range: 1
Last executed input:["cba",""]




Input:["c","c"]
Output:""
Expected:"c"

// Time:O(m*n), Space:O(m), where m is string length and n is numbers of string
public String longestCommonPrefix(String[] strs)
{




    StringBuilder res= new StringBuilder();
    // validate the input
    if ( strs== null || strs.length == 0)
       //return "";
       // NOTE: when loop stop, stringbuilder is what you want
       return res.toString();






    //boolean flag = true;
    //String prefix = new String();
    //for ( int i = 1 ; i <= strs[0].length;i++)
    //{
    //
    //      prefix = strs[0].substring(0,i);
    //      for ( int j =1; j< strs.length; j++)
    //      {
    //             if ( prefix != strs[j].substring(0,i) )
    //             {
    //               flag = false;
    //               break ;
    //             }
    //      }
    //      if (flag == false)
    //        return strs[0].substring(0,i-1);
    //}
    //if (flag == true) 
    //    return strs[0].substring(0,str[0].length);



 

     boolean sameFlag = true;
     int index = 0;




     while ( sameFlag ) 
     {



          for (int i = 0; i < strs.length ;i++)
          {
               if (str[i].length <= index  || strs[i].charAt(index) != str[0])      
               {
                     sameFlag = false;
                     break;
               } 
          }




          if (sameFlag)
          {
               res.append(strs[0].charAt(index));
               index++;
          }       




     }




     return res.toString();




}

3.Similar ones
Longest Series
(H) Longest Valid Parentheses
(M) Longest Palindromic Substring
(M) Longest Substring Without Repeating Characters



(H) Longest Consecutive Sequence