https://leetcode.com/problems/longest-substring-without-repeating-characters/
第一版
class Solution { public: string cs; int lengthOfLongestSubstring(string s) { int l = s.length(); int ans = 0; cs = s; for (int i = 0; i < l; i++) { ans = max(ans, checkNonDoublealphabets(i-ans,i)); } return ans; } int checkNonDoublealphabets(int s, int e) { bool alphabets[256] = {false}; for (int i = s; i <= e; i++) { if(alphabets[static_cast<int>(cs[i])] == true) return 0; alphabets[static_cast<int>(cs[i])] = true; } return e-s+1; } };
先做了一版slide window, length = ans, 每次都往前檢查 window內是不是有重複的字元
有的話就退出,沒有的話就把新的字元吃進來=>長度加一
大概只有50%的ranking…
第二版
class Solution { public: int lengthOfLongestSubstring(string s) { int l = s.length(); int alphabets[128] = {-1}; int ans = 0; for(int i = 0 ; i <128; i++) alphabets[i] = -1; for (int i = 0, j = i; i < l; i++) { j = i; for (; j >= i-ans; j--) { int index = alphabets[static_cast<int>(s[j])]; //update index within slides window if (index >= i-ans && index <= i && index > j) { alphabets[static_cast<int>(s[j])] = j; break; } //first time recorded alphabets[static_cast<int>(s[j])] = j; } ans = max(ans, i-j); } return ans; } };
這版優化了點 ,alphabets不用一直初始化,會記錄last s[j]最近的index,但還是只有優化一點點
而且code很不好理解,隔幾天再看我都快看不懂XD
第三版,Optimal Solution
class Solution { public: int lengthOfLongestSubstring(string s) { int l = s.length(); int alphabets[128] = {-1}; int ans = 0; for(int i = 0 ; i < 128; i++) alphabets[i] = -1; for (int i = 0, j = 0; j< l; j++) { int preIndex = alphabets[static_cast<int>(s[j])]; i = max(preIndex+1, i); ans = max(ans, j-i+1); alphabets[static_cast<int>(s[j])] = j; } return ans; } };
這應該是最佳解,關鍵是利用重複字元先前的位置,節省掉檢查slide window內重複字元的動作
i,j可以看成不重覆字元的字串的頭尾
如果發現重複字元的話,把頭的pointer i移該字元第一次出現的index之後
因為如果後面還有更長字串的話,必定不能包含這兩個字串,所以得拋棄
舉個例子好了
“aewpkwfgxyz….”
再j往下走遇到第二個字元w之前,i一直不變,遇到之後第二個w之後,i指向p這個位置
但ans沒有變,因為目前aewpk 比 pkw更長,所以ans先維持住
到後面j走到x這個位置時,新的字串pkwfgx已經比原先的 aewpk長了,就更新ans~~~