GeetCode Hub

  1. Home
  2. GeetCode
  3. GeetCode Hub

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

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

 

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

class Solution { public String longestCommonPrefix(String[] strs) { int row = strs.length; if(row == 0){ return null; } char ch = '\0'; StringBuilder sb = new StringBuilder(); for(int j=0;j<strs[0].length();j++){ for(int i=0;i<row;i++){ if(j >= strs[i].length()){ return sb.toString(); } if(i==0){ ch = strs[i].charAt(j); } else if(strs[i].charAt(j) != ch){ return sb.toString(); } } sb.append(ch); } return sb.toString(); } }

The main idea is to check each character of every word one by one, and whenever any difference is found, just return the prefix found till that point.

Time Complexity: O(m*n) //Where n is the number of words and m is the average length of the word.

Space Complexity: O(m) // To store the result in string builder.