[Leetcode] 14. Longest Common Prefix

14. Longest Common Prefix

• Hardness: \(\color{green}\textsf{Easy}\)
• Ralated Topics: String

一、題目

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.

二、分析

• 簡單的字串比對問題。
• 需熟悉 string 的函數 substr() 的使用方式，常用以下兩種
  • s.substr(int start, int len)，從 start 起取長度為 len 的子字串。
  • s.substr(int start) 從 start 起取到字串的結尾。

三、解題

1. String

• Time complexity: \(O(m\times n)，\text{m }為\text{ strs }的長度，\text{n }為\text{ strs[i] }的長度\)，
• Space complexity: \(O(1)\)

string longestCommonPrefix(vector<string>& strs) {
    string res = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        int j = 0;
        for (; j < min(strs[i].length(), res.length()); j++) {
            if (strs[i][j] != res[j]) break;
        }
        res = res.substr(0, j);
    }
    return res;
}

回目錄 Catalog