Rex-Software-Blog

[LeetCode]

003-Longest Substring Without Repeating Characters

簡介

題目要求從給定字串中找出最長且無重複的子字串(Substtring)，

因需求子字串而非子序列所以必須是連續的，

解題概述

若一字串為"abcabcbb"，找出無重複最長子字串，

首先一個字元一個字元遍歷，得a,b,c後，又出現一個a，此時應去掉第一個a，

繼續遍歷，又出現一個b，則去掉第一個b，

以此類推，最後發現結果為a,c,b

實際解題

由於有去除字元的動作，因此我們需要紀錄出現過的字元的位置，

所以應用Hash table( dict( ) )來對照字元及位置，

根據解題概述可以了解實際在找出子字串就是在給定字串上滑動一個窗口(window)，

窗口內不得有重複字元，且需要盡可能擴大窗口，也就是無重複最長子字串，

窗口會持續向右滑動，所以只需紀錄每個字元最後出現的位置，並紀錄在Hash table( dict( ) )中，

窗口的右邊界就是目前遍歷到的字元的位置，而為了求出窗口大小，也需要窗口左邊界，

若窗口右邊界遍歷到的字元未出現過，直接擴大右邊界，

若窗口右邊界遍歷到的字元有出現過，分為兩種情況 : 

• 若不在窗口內，直接將該字元納入窗口
• 若在窗口內，便在窗口內去掉這個已經存在的重複字元，再納入該字元

由於已將每個字元最後出現的位置紀錄在Hash table( dict( ) )中，因此只要移動窗口左邊界至該字元位置即可

最後再由左邊界減去右邊界得到最終窗口大小。