Question

Formatted question description: https://leetcode.ca/all/14.html

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

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.

Algorithm

Algorithm Explanation:

Initialize two variables, i and j, where i will traverse the characters in the search string, and j will traverse each string in the string set.
Since the words are arranged vertically, it can be considered as 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.
The common prefix that has been found cannot be longer than the shortest word, so the common prefix that has been found is returned at this time.
Take out the character 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 any character is not equal, return the result. If all characters are the same, save the current character in the result and continue checking the character in the next position.

Improved Algorithm Explanation:

Initialize two variables, i and j, where i will traverse the characters in the search string, and j will traverse each string in the string set.
Consider the string set as a 2D array with unequal line lengths, with the characters arranged vertically. Traverse the array vertically instead of horizontally.
Since the common prefix cannot be longer than the shortest word, return the common prefix once its length equals the length of the shortest word.
Take out the character 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 any character is not equal, return the result. If all characters are the same, save the current character in the result and continue checking the character in the next position.

Code

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++;
			}

		}
	}
}

############

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        for (int i = 0; i < strs[0].length(); ++i) {
            for (int j = 1; j < n; ++j) {
                if (strs[j].length() <= i || strs[j].charAt(i) != strs[0].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

// OJ: https://leetcode.com/problems/longest-common-prefix/
// 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:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(len(strs[0])):
            for s in strs[1:]:
                if len(s) <= i or s[i] != strs[0][i]:
                    return s[:i]
        return strs[0]

############

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]

func longestCommonPrefix(strs []string) string {
	n := len(strs)
	for i := range strs[0] {
		for j := 1; j < n; j++ {
			if len(strs[j]) <= i || strs[j][i] != strs[0][i] {
				return strs[0][:i]
			}
		}
	}
	return strs[0]
}

function longestCommonPrefix(strs: string[]): string {
    const len = strs.reduce((r, s) => Math.min(r, s.length), Infinity);
    for (let i = len; i > 0; i--) {
        const target = strs[0].slice(0, i);
        if (strs.every(s => s.slice(0, i) === target)) {
            return target;
        }
    }
    return '';
}

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    for (let j = 0; j < strs[0].length; j++) {
        for (let i = 0; i < strs.length; i++) {
            if (strs[0][j] !== strs[i][j]) {
                return strs[0].substring(0, j);
            }
        }
    }
    return strs[0];
};

# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
  return '' if strs.nil? || strs.length.zero?

  return strs[0] if strs.length == 1

  idx = 0
  while idx < strs[0].length
    cur_char = strs[0][idx]

    str_idx = 1
    while str_idx < strs.length
      return idx > 0 ? strs[0][0..idx-1] : '' if strs[str_idx].length <= idx

      return '' if strs[str_idx][idx] != cur_char && idx.zero?
      return strs[0][0..idx - 1] if strs[str_idx][idx] != cur_char
      str_idx += 1
    end

    idx += 1
  end

  idx > 0 ? strs[0][0..idx] : ''
end

using System.Text;
using System.Linq;

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs.Length == 0) return string.Empty;
        var sb = new StringBuilder();
        for (var i = 0; i < strs[0].Length; ++i)
        {
            var ch = strs[0][i];
            if (strs.All(str => str.Length > i && str[i] == ch))
            {
                sb.Append(ch);
            }
            else
            {
                break;
            }
        }
        return sb.ToString();
    }
}

impl Solution {
    pub fn longest_common_prefix(strs: Vec<String>) -> String {
        let mut len = strs.iter().map(|s| s.len()).min().unwrap();
        for i in (1..=len).rev() {
            let mut is_equal = true;
            let target = strs[0][0..i].to_string();
            if strs.iter().all(|s| target == s[0..i]) {
                return target;
            }
        }
        String::new()
    }
}

class Solution {
    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        $rs = "";
        for ($i = 0; $i < strlen($strs[0]); $i++) {
            for ($j = 1; $j < count($strs); $j++) {
                if ($strs[0][$i] != $strs[$j][$i]) return $rs;
            }
            $rs = $rs.$strs[0][$i];
        }
        return $rs;
    }
}

14 - Longest Common Prefix

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions