Question
Formatted question description: https://leetcode.ca/all/14.html
14 Longest Common Prefix
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: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters az.
@tagstring
Algorithm
There is no special skill, just a brainless search, define two variables i and j, where i is to traverse the characters in the search string, and j is to traverse each string in the string set.
Here, if the words are arranged up and down, it is equivalent to a twodimensional array with unequal line lengths. The traversal order is different from the general horizontal linebyline traversal. Instead, the vertical traversal is adopted. No, it means it is the shortest word, because the length of the common prefix cannot be longer than the shortest word, so the common prefix that has been found is returned at this time.
Take out the word at a certain position of the first string each time, and then traverse the corresponding positions of all other strings to see if they are equal, if there are unsatisfied, return res directly, if they are all the same, save the current character in the result, continue Check the character in the next position.
Code
Java

public class Longest_Common_Prefix { public class Solution { public String longestCommonPrefix(String[] s) { if (s == null  s.length == 0) { return ""; } int i = 0; StringBuilder result = new StringBuilder(); while (true) { for (String each : s) { if (i >= each.length()  each.charAt(i) != s[0].charAt(i)) { return result.toString(); } } result.append(s[0].charAt(i)); i++; } } } }

// OJ: https://leetcode.com/problems/longestcommonprefix/ // Time: O(NW) // Space: O(1) class Solution { public: string longestCommonPrefix(vector<string>& A) { int len = A[0].size(); for (int i = 1; i < A.size() && len; ++i) { int j = 0, end = min(len, (int)A[i].size()); while (j < end && A[0][j] == A[i][j]) ++j; len = j; } return A[0].substr(0, len); } };

class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if len(strs) == 0: return "" i = 0 j = 0 end = 0 while j < len(strs) and i < len(strs[j]): if j == 0: char = strs[j][i] else: if strs[j][i] != char: break if j == len(strs)  1: i += 1 j = 0 end += 1 else: j += 1 return strs[j][:end]