DOJO004

Dashool 創辦人
喜歡調酒
Rails、Nextjs、TypeScript

來刷 LeetCode 吧! 10 14.Longest Common Prefix

LeetCode

https://leetcode.com/problems/longest-common-prefix/description/

題目分析

提供一個字串的陣列，找到這些字串的共同前綴並回傳。若沒有共同前綴，回傳 “”。

第一直覺(錯誤)

我先將 strs 做排序，將短字串放前面，長字串放後面，這樣只要比較頭尾兩個字串。

var longestCommonPrefix = function (strs) {
  let result = "";
  let newStrs = strs.sort((a, b) => a.length - b.length);

  for (let i = 0; i < newStrs[0].length; i++) {
    if (newStrs[0][i] === newStrs[newStrs.length - 1][i]) {
      result += newStrs[0][i];
    } else {
      break;
    }
  }

  return result;
};

console.log(longestCommonPrefix(["flower", "flow", "flight"])); // "fl"
console.log(longestCommonPrefix(["dog", "racecar", "car"])); // ""
console.log(longestCommonPrefix(["abab", "aba", "abc"])); // "ab" error output: aba

優化作法

上面的作法很接近了，但還差了一點。

其實不用排序，直接取得第一個字串再與其他字串做比較。

var longestCommonPrefix = function (strs) {
  if (strs.length === 0) return "";

  // 取出第一個字符串作為參考
  let prefix = strs[0];

  for (let i = 1; i < strs.length; i++) {
    // 將參考前綴與每個字符串比較，找出共同前綴
    while (strs[i].indexOf(prefix) !== 0) {
      // 不斷減少參考前綴的長度，直到找到共同前綴或變成空
      prefix = prefix.slice(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }

  return prefix;
};