LeetCode 3. Longest Substring Without Repeating Characters

2017-03-07

748
0
LeetCode 練功房
2017-03-08

LeetCode 第三題 "Longest Substring Without Repeating Characters"

題目說明：給一字串 s，找到在 s 中不重複字母的最長字段長度。

Step 1: 新增測試案例，s 長度為 1 時，應回傳 1

測試代碼：

    [TestClass]
    public class UnitTest1
    {
        [TestMethod]
        public void s_is_a_should_return_1()
        {
            var s = "a";
            Assert.AreEqual(1, new Solution().LengthOfLongestSubstring(s));
        }
    }

生產代碼：

    public class Solution
    {
        public int LengthOfLongestSubstring(string s)
        {
            throw new NotImplementedException();
        }
    }

Step 2: 回傳 s 長度，以通過測試案例

生產代碼：

重構測試代碼：extract method AssertLength() 簡化測試案例撰寫

Step 3: 新增一個字母重複的測試案例，s_is_bb_should_return_1

測試代碼：

生產代碼：使用 HashSet<char> 排除字母重複的情況

Step 4: 新增測試案例，因字母重複截斷字段，s_is_pwwkew_length_should_be_3

測試代碼：若只有用 HashSet, 實際結果會是 4, 也就是 "pwke" 而期望的最長字段應該是 "wke"

生產代碼：當發現字母重複時，目前 HashSet 所代表的字段長度與目前暫存的最大長度，取最大值暫存後，清除 HashSet 以存放下一個不重複字母的字段。

Step 5: 新增測試案例，碰到重複字母後，游標重置問題，s_is_dvdf_length_should_be_3

測試代碼：以目前的生產代碼，當 "dvdf" 巡覽至第二個 d 時，會將 dv 清空，長度為 2，並從第二個 d 開始巡覽至 f，所以最大長度為 2。但期望的結果是 "vdf" 長度應為 3。

生產代碼：改使用 Dictionary 紀錄 char 與其在 s 中的 index 位置來取代 HashSet 沒有 index 可用的問題。當發生字母重複時，應將游標重置至重複的字母第一個位置。

重構：移除 s 長度為 1 的判斷，因為已經被後面實作邏輯包含。

最終生產代碼版本

    public class Solution
    {
        public int LengthOfLongestSubstring(string s)
        {
            var charArray = s.ToCharArray();

            var longestWord = new Dictionary<char, int>();
            var index = 0;
            var lastLongestWordLength = 0;

            while (index < charArray.Length)
            {
                var c = charArray[index];

                if (longestWord.ContainsKey(c))
                {
                    lastLongestWordLength = Math.Max(lastLongestWordLength, longestWord.Count);
                    index = longestWord[c];
                    longestWord.Clear();
                }
                else
                {
                    longestWord.Add(c, index);
                }

                index++;
            }

            return Math.Max(lastLongestWordLength, longestWord.Count);
        }
    }