Merge pull request soulmachine#64 from LiEmail/patch-2

soulmachine · soulmachine · commit 44c0c6ae3734 · 2016-01-07T22:13:04.000-08:00
Longest Substring Without Repeating Characters
diff --git a/C++/chapGreedy.tex b/C++/chapGreedy.tex
@@ -282,21 +282,22 @@ \subsubsection{代码}
 \begin{Code}
 // LeetCode, Longest Substring Without Repeating Characters
 // 时间复杂度O(n)，空间复杂度O(1)
+// 考虑非字母的情况
 class Solution {
 public:
     int lengthOfLongestSubstring(string s) {
-        const int ASCII_MAX = 26;
+        const int ASCII_MAX = 255;
         int last[ASCII_MAX]; // 记录字符上次出现过的位置
         int start = 0; // 记录当前子串的起始位置
 
         fill(last, last + ASCII_MAX, -1); // 0也是有效位置，因此初始化为-1
         int max_len = 0;
         for (int i = 0; i < s.size(); i++) {
-            if (last[s[i] - 'a'] >= start) {
+            if (last[s[i]] >= start) {
                 max_len = max(i - start, max_len);
-                start = last[s[i] - 'a'] + 1;
+                start = last[s[i]] + 1;
             }
-            last[s[i] - 'a'] = i;
+            last[s[i]] = i;
         }
         return max((int)s.size() - start, max_len);  // 别忘了最后一次，例如"abcd"
     }
