LeetCode 3. Longest Substring Wi

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 長度，以通過測試案例

生產代碼：

baby step 通過測試用例

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

擷取方法 AssertLength()

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

測試代碼：

s 為 2 個重複字母

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

使用 HashSet 排除重複

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

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

不重複字母總數為4, 不重複字母最長字段為3

生產代碼：當發現字母重複時，目前 HashSet 所代表的字段長度與目前暫存的最大長度，取最大值暫存後，清除 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 可用的問題。當發生字母重複時，應將游標重置至重複的字母第一個位置。

使用 Dictionary 找第一個重複字母的 index 位置，進行游標重置

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

refactor 生產代碼

重構：rename 後得到最終生產代碼版本

    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);
        }
    }

通過 LeetCode 上所有測試案例

pass LeetCode all test cases

結論

可以試著把 LeetCode 當作線上版本的驗證。當自己覺得已經完成滿足需求的生產代碼時，丟上去 LeetCode 跑，失敗的測試案例就像沒測到的 bug, 將代表這個 bug 的測試案例加入測試專案後，確保已將此 bug 修復完成且過去的測試案例都仍如預期正常運作，代表可以再更版上線。挺好玩的！

GitHub commit history: LeetCode_3_Longest_Substring