Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Longest Common Prefix]，這在 LeetCode 算是比較簡單的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

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

1
2
3
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.

自已解法

這個題目我原本以為是抓最多次出現的前綴詞，後來嘗試後才理解，原來是取得最長的前綴詞字串，首先我們先定義前綴詞為第一個值。

1
2
3
4
5
6
7
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let prefix = strs[0];
}

我們透過陣列來列出每一個值去做比較，接著透過while的方式去判斷目前的前綴詞，透過indexOf來確認目前是否有吻合前綴詞，如果沒有吻合，那我們從最後面開始減少，假設初始prefix='flower'，那接下來prefix=flowe，接著繼續判斷，除此之外為了以防扣除到後面prefix為空導致無限迴圈，我們需要做個小例外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let prefix = strs[0];

    for(let word of strs) {
        while(word.indexOf(prefix) !== 0) {
            prefix = prefix.slice(0, -1);
            if (prefix === '') return '';
        }
    }
    return prefix;
}

實作結果

如此一來他會一直往下去尋找直至有吻合的前綴詞。

Image From LeetCodeImage From LeetCode