LeetCode Python/Java/C++/JS  >  14. Longest Common Prefix  >  Solved in Ruby, Python, Java  >  GitHub

    LeetCode link: 14. Longest Common Prefix, difficulty: Easy.

    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 if it is non-empty.
    Topics

    String

    Intuition
    PreviousNext

    1. To find the longest common prefix, you can scan from left to right, using the characters of the first string as the baseline.
    2. If the current character in the other strings does not match the baseline character, return the result. After each round of iteration, add the baseline character to the common prefix.

    👋 Hi, I'm the developer behind coder.id — Build your programmer brand. Create your portfolio, resume, and blog in minutes, and land your dream offer!

    Complexity

    Time complexity

    O(M * N)

    Space complexity

    O(1)

    Solution in languages: Ruby Python Java

    Ruby # 

    # @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
  result = ''

  (0...strs[0].size).each do |i|
    char = strs[0][i]

    strs[1..].each do |str|
      if str[i] != char
        return result
      end
    end

    result << char
  end

  result
end

    Python # 

    class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        result = ''

        for i in range(len(strs[0])):
            char = strs[0][i]

            for string in strs[1:]:
                if i >= len(string) or string[i] != char:
                    return result

            result += char

        return result

    Java # 

    class Solution {
    public String longestCommonPrefix(String[] strs) {
        var result = "";

        for (var i = 0; i < strs[0].length(); i++) {
            var c = strs[0].charAt(i);

            for (var j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return result;
                }
            }

            result += c;
        }

        return result;
    }
}
    Solution in languages: Ruby Python Java

    Other languages

    Welcome to contribute code to GitHub repo -> 14. Longest Common Prefix. Thanks!
    PreviousNext

    Level Up Your Developer Identity

    • 📄 Resume, Portfolio & Blog
    • 🌐 Custom Domain Binding Supported
    • ✨ Premium Subdomain: https://yourname.coder.id

    Build Your Developer Brand at coder.id →