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.
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]consists of only lower-case English letters.
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.