Sunday, January 11, 2015

14. Longest Common Prefix Leetcode Java

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

Solution:
Use first String in the array as reference, compare all other arrays with it char by char. If any string has disagree char, return the current prefix, other wise add the processing char to the result common prefix.
Time complexity:O(m*n) m is Array Length, n is the prefix length.


 public String longestCommonPrefix(String[] strs) {  
    if(strs==null || strs.length==0) return "";  
    StringBuilder sb=new StringBuilder();  
    for(int i=0;i<strs[0].length();i++){  
      for(int j=1;j<strs.length;j++){  
        if(i>=strs[j].length()) return sb.toString();  
        if(strs[j].charAt(i)!=strs[0].charAt(i)) return sb.toString();  
      }  
      sb.append(strs[0].charAt(i));  
    }  
    return sb.toString();  
   }  

No comments:

Post a Comment