LeetCode 3. Longest Substring Without Repeating Characters

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

通過 LeetCode 上所有測試案例

結論

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

GitHub commit history: LeetCode_3_Longest_Substring

對敏捷開發有興趣的朋友,可以參考我的粉絲專頁:91敏捷開發之路

若需要聯絡我,可以透過粉絲專頁私訊或是側欄的關於我。