14.Longest Common Prefix

Posted on | In

Question：

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:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

My answer (java)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
  public String longestCommonPrefix(String[] strs) {
      if (strs.length == 0) 
          return "";
      String str1 = strs[0];
      for(int i=0;i<str1.length();i++){
          for(int j=1;j<strs.length;j++){
              if(i==strs[j].length() || str1.charAt(i)!=strs[j].charAt(i))
                  return str1.substring(0,i);
          }               
      }
      return str1;
  }
}

Running time: 12ms