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 "".
Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.
Solutions (Click to expand)
Check that every ith character of every string is the exact same. Once you reach the first non-matching ith character you can concluded that substring from beginning to i (non-inclusive) of every string is the exact same. You can also instead reach the end of the shortest string for which you can say that substring from beginning to min(strs).length (non-inclusive) of every string is the exact same. In the case that all string are the exact same you can return the first string.