#LeetCode:3. Longest Substring Without Repeating Characters

用 Sliding Window 的方式,用前後兩個 index 去紀錄目前所找到的子字串。

每次往後延伸 Window 時,先檢查前面是否有重複出現過該字母,若有就把頭移到重複出現的該字母前一次出現的 index 的後面一位,如果前一次的 index 已經不在所夾住的子字串中則忽略。接著再將目前往後延伸到的字母所在 index 給記錄下來,以利之後的查找。這樣在每次延伸出來的子字串中找出最長的長度即是答案。

C++(46ms)

/*******************************************************/
/* LeetCode 3. Longest Substring Without Repeating     */
/*             Characters                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/05/23                                 */
/*******************************************************/
class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    map<char, int> currentIndexMap;

    int sLength = s.length();
    int maxSubstringLength = 0;
    int head = 0;
    for(int i = 0 ; i < sLength ; ++i){
      if(currentIndexMap.find(s[i]) != currentIndexMap.end()){
        head = max(currentIndexMap[s[i]] + 1, head);
      }

      currentIndexMap[s[i]] = i;
      maxSubstringLength = max(maxSubstringLength, i - head + 1);
    }

    return maxSubstringLength;      
  }
};

廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: