Day20-[Grind 169 questions][String] LeeCode 438、49、424

2023 iThome 鐵人賽

DAY 20

自我挑戰組

那些年我沒寫到的資料結構和 LeetCode 題目練習系列第 20 篇

15th鐵人賽資料結構與演算法 javascript leetcode leetcode 刷題紀錄

harry xie

團隊大船要開囉

2023-10-05 18:33:21

270 瀏覽

分享至

438. Find All Anagrams in a String

解題程式碼

const alphabets = 'abcdefghijklmnopqrstuvwxyz';

const sameMap = (obj1, obj2) => {
  for (let i in obj1) {
    if (obj1[i] !== obj2[i]) return false;
  }
  return true;
};

var findAnagrams = function (s, p) {
  const indexs = [];
  const objS = {};
  const objP = {};

  for (let alphabet of alphabets) {
    objP[alphabet] = 0;
    objS[alphabet] = 0;
  }

  for (let i = 0; i < p.length; i++) {
    objP[p[i]]++;
    objS[s[i]]++;
  }

  for (let i = 0; i <= s.length - p.length; i++) {
    if (sameMap(objP, objS)) {
      indexs.push(i);
    }
    objS[s[i]]--;
    objS[s[i + p.length]]++;
  }

  return indexs;
};

解題思路、演算法

這題可以使用 Sliding Window 和 hashTable 解題，首先建立兩個 hashTable，初始化將每個字母都加入到 hashTable 裡，然後將 p 長度內的字母出現次數計入到 hashTable。

之後遍歷 s 字串(到 s.length - p.length 為止，因為子字串長度小於 p 一定不能重組成 p)，若兩個 hashTable 內容相同，就是 Anagram，並且每次遍歷字母都將當前字母從 hashTable 扣掉，並加入新的字母(位置為 i + p.length)。

解法的時間、空間複雜度

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

參考資料

Find All Anagrams in a String - LeetCode

看底下的 Sliding Window Technique，是執行效率較好的做法

花花酱 LeetCode 438. Find All Anagrams in a String - 刷题找工作 EP191

49. Group Anagrams

解題程式碼

解法 1.

var groupAnagrams = function (strs) {
  const strMap = new Map();
  const sortStrs = [...strs].map((str) => str.split('').sort().join(''));
  const result = [];

  for (let i = 0; i < strs.length; i++) {
    if (!strMap.has(sortStrs[i])) {
      strMap.set(sortStrs[i], [strs[i]]);
    } else {
      strMap.set(sortStrs[i], [...strMap.get(sortStrs[i]), strs[i]]);
    }
  }

  strMap.forEach((value) => {
    result.push(value);
  });
  return result;
};

解法 2.

var groupAnagrams = function (strs) {
  const strMap = new Map();
  const result = [];

  for (let i = 0; i < strs.length; i++) {
    const count = new Array(26).fill(0);

    for (let char of strs[i]) {
      // 97 === a Unicode value
      count[char.charCodeAt() - 97]++;
    }

    let key = count.join('#');
    if (!strMap.has(key)) {
      strMap.set(key, [strs[i]]);
    } else {
      strMap.set(key, [...strMap.get(key), strs[i]]);
    }
  }

  strMap.forEach((value) => {
    result.push(value);
  });

  return result;
};

解題思路、演算法

解法 1.

將 strs 陣列內的字串都根據字母做排序，然後用 hashMap 儲存其排序後的值當作 key，排序前的字串組成一個陣列放在一起，最後所有 hashMap 的值取出來就是題目要的結果。

new Map([
  ['aet', ['eat', 'tea', 'ate']],
  ['ant', ['tan', 'nat']],
  ['abt', ['bat']],
]);

解法 2.

將 strs 陣列內的字串記錄其出現的字母和其次數，當作 hashMap 的 key，例如 aet，就是以 "1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0" 當作 key，這樣也能找到 value ['eat', 'tea', 'ate']，降低了第一個解法的時間複雜度。

new Map([
  ['1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0', ['eat', 'tea', 'ate']],
  ['1#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#1#0#0#0#0#0#0', ['tan', 'nat']],
  ['1#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0', ['bat']],
]);

解法的時間、空間複雜度

解法 1.

時間複雜度: O(m * n * log k)，m 為陣列元素數目，n 是陣列元素中字串平均長，然後做 sort 所以 n _ log k。
空間複雜度: O(n * k)

解法 2.

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

參考資料

424. Longest Repeating Character Replacement

解題程式碼

var characterReplacement = function(s, k) {
    let maxLength = 1;
    let l = 0;
    const charMap = new Map();
    let maxRepeat = 0;

    for (let i = 0; i < s.length; i++) {
        charMap.set(s[i], (charMap.get(s[i]) || 0) + 1);
        maxRepeat = Math.max(maxRepeat, charMap.get(s[i]));

        while (i - l + 1 - maxRepeat > k) {
            charMap.set(s[l], charMap.get(s[l]) - 1);
            l++;
        }
        maxLength = Math.max(maxLength, i - l + 1);
    }

    return maxLength;
};

// input = 'AABCDAAA'，k = 2
// i = 0, l = 0, maxRepeat = 1 maxLength = 1
// i = 1, l = 0, maxRepeat = 2 maxLength = 2
// i = 2, l = 0, maxRepeat = 2 maxLength = 3
// i = 3, l = 0, maxRepeat = 2 maxLength = 4
// i = 4, l = 0, maxRepeat = 2 maxLength = 4，進 while, window = ABCD
// i = 4, l = 1, maxRepeat = 1 maxLength = 4，進 while, window = BCD
// i = 4, l = 2, maxRepeat = 1 maxLength = 4
// i = 5, l = 2, maxRepeat = 1 maxLength = 4，進 while, window = CDA
// i = 5, l = 3, maxRepeat = 1 maxLength = 4
// i = 6, l = 3, maxRepeat = 2 maxLength = 4，CDAA
// i = 7, l = 3, maxRepeat = 3 maxLength = 5，CDAAA

解題思路、演算法

這題使用 Sliding Window 解題，我們可以使用一個 hashTable 或是長度 26 個元素的陣列去儲存一個字串內各字母出現的次數，並記錄當前 window 內出現最多次的字母次數 maxRepeat，當 window size - maxRepeat <= k 時，例如 AABDA，k = 2，最多可以使用兩次去替換掉非出現最多次字母的那些字母，那 5 - 3 <= 2 成立，故 5 有可能就是題目要求的結果之一，依照這個邏輯不斷滑動窗口到字串尾端，即可找出結果。