【LeetCode】Longest Substring Without Repeating Characters 解法【Python】
スポンサードリンク
Longest Substring Without Repeating Characters
与えられた文字列内で、文字が重複しない範囲の最大の文字数を返却する。
解法
1文字見ていって、重複した時点の1文字前までの文字数を最大候補として、 重複した文字の最初に出てきた場所から再度カウントし直す。 それを繰り返して最大候補の中から最大文字数を返却する。
毎回、重複した文字の最初に出てきた文字まで戻るのはコストなので、 その場所を覚えておき、現在の場所までの文字列をスライス、みたいなふうにして高速化。
コード
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s == "": return 0 if len(set(s)) == len(s): return len(s) max_len = str_len = 1 local_s = [s[0]] s_idx = 0 for i in range(1, len(s)): if s[i] in local_s: str_len = i - s_idx max_len = max(max_len, str_len) find_idx = local_s.index(s[i]) s_idx = find_idx+s_idx+1 local_s = local_s[find_idx+1:] local_s.append(s[i]) else: str_len = len(s) - s_idx max_len = max(max_len, str_len) return max_len
ハッシュ使ったらもっと速そう。
solutionに書いていたシンプルなコード(にちょっとだけ手を加えて高速化したもの)
class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ str_list = [] max_length = 0 for x in s: if x in str_list: max_length = max(max_length, len(str_list)) str_list = str_list[str_list.index(x)+1:] str_list.append(x) else: max_length = max(max_length, len(str_list)) return max_length
さらに、solutionに書いていた、めちゃ速い解法。 やはりdict使っている。
class Solution: def lengthOfLongestSubstring(self, s): dicts = {} maxlength = start = 0 for i,value in enumerate(s): if value in dicts: sums = dicts[value] + 1 if sums > start: start = sums num = i - start + 1 if num > maxlength: maxlength = num dicts[value] = i return maxlength