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 lowercase English letters if it is non-empty.
Solutions
Solution 1: Character Comparison
Thinking
The first idea is to take the first string as the prefix and shrink it against each later string. \(n,m\le 200\), so even a triple loop would pass. A trie works too, but it is heavier than this problem needs.
The prefix only ever shrinks: once a column disagrees, a longer prefix cannot exist. Align the strings vertically; position \(i\) can extend the prefix only if every string matches there.
So we compare column by column against \(\textit{strs}[0]\) and return as soon as a string is too short or a character differs. No trie.
We use the first string \(\textit{strs}[0]\) as a benchmark, and compare whether the \(i\)-th character of the subsequent strings is the same as the \(i\)-th character of \(\textit{strs}[0]\). If they are the same, we continue to compare the next character. Otherwise, we return the first \(i\) characters of \(\textit{strs}[0]\).
If the traversal ends, it means that the first \(i\) characters of all strings are the same, and we return \(\textit{strs}[0]\).
The time complexity is \(O(nm)\), and the space complexity is \(O(1)\), where \(n\) and \(m\) are the length of the string array and the minimum length of the strings, respectively.