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