14. Longest Common Prefix

解題程式碼

var longestCommonPrefix = function (strs) {
  if (strs.length === 0) return '';
  let result = strs[0];
  let currentIndex = 1;

  while (currentIndex < strs.length) {
    // ex: console.log("hello world".indexOf("he")); // 0
    // 和當前遍歷到的字串比對
    while (strs[currentIndex].indexOf(result) !== 0) {
      result = result.slice(0, -1); // 移除最後字元
    }
    currentIndex++;
  }

  return result;
};

解題思路、演算法

一開始先將陣列內第一個字串存在要回傳的結果字串變數，然後我們去和陣列內第二個之後的字串做比對

如果結果字串不存在於當前遍歷到的字串，就不斷把結果字串後的字母移除，這樣一來越到後面結果字串會越來越短，因為一直把不相符的字串剔除

解法的時間、空間複雜度

時間複雜度: O(n * k)，n 為字串長度，k 為陣列內的字串數量
空間複雜度: O(n)

參考資料

179. Largest Number

解題程式碼

var largestNumber = function (nums) {
  nums = nums.sort((a, b) => ('' + a + ('' + b) > '' + b + ('' + a) ? -1 : 1));
  if (nums[0] === 0) return '0';
  return nums.join('');
};

解題思路、演算法

一開始想到的是要讓陣列的值以字串的形式合併後要找到最大值，那肯定 9 開頭的數字要放在前面，而 1 開頭的數字放後面，將陣列依照上述邏輯做單純的降冪排列會發生一個問題，相同開頭的數字排序後，兩者合併得出的值不一定最大。

ex: [ 927535, 92753, 9275, 927 ] 為排序後的陣列，92753927535 > 92753592753，故要想其他的邏輯去做排序，而這題可以將兩字串相加後去比大小做排序，s1+s2 > s2+s1。

// [3,30,34,5,9] "9534 3 30"
// [3,35,34,5,9] "9535 34 3"
// [3,34,34,5,9] "9534 34 3"
// [3,32,34,5,9] "9534 3 32"

解法的時間、空間複雜度

時間複雜度: O(n * log n)
空間複雜度: O(n)

參考資料

Largest Number - Leetcode 179 - Python

271. Encode and Decode Strings

題目說明

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Example 1:

Input: ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation:
One possible encode method is: "lint:;code:;love:;you"

Example 2:

Input: ["we", "say", ":", "yes"]
Output: ["we", "say", ":", "yes"]
Explanation:
One possible encode method is: "we:;say:;:::;yes"

解題程式碼

class Solution {
  encode(strs) {
    let encoded = '';
    for (let str of strs) {
      encoded += str.length + '/' + str;
      for (const element of array1) {
        console.log(element);
      }
    }
    return encoded;
  }

  decode(s) {
    let strs = [];
    let i = 0;
    while (i < s.length) {
      let slash = s.indexOf('/', i);
      let len = Number(s.substring(i, slash));
      i = slash + len + 1;
      strs.push(s.substring(slash + 1, i));
    }
    return strs;
  }
}

解題思路、演算法

分別寫出編碼字串和解碼字串的函式。編碼字串的函式，透過特殊字元將多個字串聯接在一起，但如果字串本身就包含特殊字元，在解碼時就會不知道怎麼解，所以再將字串長度加入到字串前，例如 ["lint","code","love","you"] 經過編碼後就變成 4/lint4/code4/love3/you。

解碼字串的函式，要想辦法把編碼後的字串取出原本的字串，以 4/lint4/code4/love3/you 為例，可以找到 /，字串長度就是 / 的前一個字元，取得字元數和當前遍歷字串的 pointer 就可以一個個把把編碼前的字串找出了。

複習: Array.prototype.indexOf() 第二個參數代表陣列中搜尋的起始索引

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: encode: O(1)，decode: 0(n)

參考資料

[Leetcode]271. Encode and Decode Strings