LeetCode (Algorithms#14) ‒ Longest Common Prefix

Problem

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

Solution

For a set of $n$ strings, the brute force solution is sufficient as you must compare a character in each string to determine if it belongs to a common prefix. Thus, the optimal solution is $O(n^2)$, where the worst case is all strings match.

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$
Runtime: 12ms (52.13%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public String longestCommonPrefix(String[] strs) { if (strs.length==0 || strs[0].length()==0) return ""; else if (strs.length==1) return strs[0]; StringBuilder sb = new StringBuilder(); int j = 0; char prefChar; boolean isPrefChar; while (j<strs[0].length()) { prefChar = strs[0].charAt(j); isPrefChar = true; for (int i=1; i<strs.length; i++) isPrefChar &= j<strs[i].length() && strs[i].charAt(j)==prefChar; if (isPrefChar) sb.append(prefChar); else break; j++; } return sb.toString(); }