Formatted question description:

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.

All given inputs are in lowercase letters a-z.



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 two-dimensional array with unequal line lengths. The traversal order is different from the general horizontal line-by-line 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.



    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();
  • // OJ:
    // Time: O(NW)
    // Space: O(1)
    class Solution {
        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]
            if strs[j][i] != char:
          if j == len(strs) - 1:
            i += 1
            j = 0
            end += 1
            j += 1
        return strs[j][:end]

All Problems

All Solutions