LeetCode #3 "longest-substring-without-repeating-characters"
上から3番目の問題を解く。
問題文
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
与えられた文字列の中から、最長の部分文字列の長さを求めよというもの。部分文字列は重複した文字を含んではいけない。
考えたこと
与えられた文字列を1文字ずつ取得し、新しい部分文字列を作成していく。新しい部分文字列の中で重複が発生したら、その部分文字列を重複位置より前を削る。これが基本的な考え方になるだろう。
新しい部分文字列の中で重複が発生したことを、どうやって検知すればよいか？これには、ハッシュを使ってみる。
重複を見つけた場合、文字列内の探索位置を巻き戻すのか、新しい部分文字列を削るだけにしておいて探索位置をそのままにしておくのか、どちらがいいのだろう？
探索位置を巻き戻す場合、ハッシュと部分文字列を全クリアするだけで済む。実装としてはとてもシンプルになる。一方、新しい部分文字列を削って探索位置を巻き戻さない方法を採る場合、削った文字の分だけハッシュの要素も削除しなければならない。これはちょっと面倒そう。探索位置を巻き戻す方法を採ってみることにする。
コード
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0;
std::unordered_map<char, int> um;
auto size = 0;
for(auto i = 0u; i < s.size(); i++){
if(um.find(s[i]) != um.end()){
if(ret < size){
ret = size;
}
i = um[s[i]] + 1;
um.clear();
size = 0;
}
size++;
um[s[i]] = i;
}
return ret > size ? ret : size;
}
};模範解答は？
自分の解答について、パスはしたものの、RunTimeなどの指標があまり良くない。模範解答を見たところ、"Sliding Window"というアルゴリズムが一般的にあるらしく、それを使えということらしい。
部分文字列の始端を覚えておき、終端を伸ばしていく感じ。終端で重複が見つかったら始端を一つずらす。このときは終端は動かさない。これを与えられた文字列の終端まで繰り返す。重複チェックにはハッシュを用いる。これだけ。
考え方として、方向性として、自分の考えていたものとそう大きくは違わない。部分文字列側の始端を覚えておいて、重複発生時にはそちらを一文字ずつ動かすことでハッシュと部分文字列側を一文字ずつ処理していくだけだ。
これ、自分で導き出したかったなあ～。