LeetCode第3題(Longest Substring Without Repeating Characters)

LeetCode第3題(Longest Substring Without Repeating Characters)

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, 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つの文字列の最長の重複のないサブ列を求めます.比較的簡単なテーマでもあります.関連する知識点は、主に文字列操作と文字が重複しているかどうかを決定する方法です.文字列を巡回するにはiteratorを使用します.1つの文字に使用可能なセットタイプが現れたかどうかを判断します.そこで、プログラムにstd::set型変数dictを設定しました.1文字がdictに存在するか否かを判断するにはcount()メソッドを用い,0を返してこの文字が存在しないことを示す.文字を追加するにはinsertメソッドを使用し、文字を削除するにはeraseメソッドを使用します.
もう一つのポイントは、この文字列をどのように巡るかです.私のプログラムではヘッダーとテールの2つのポインタを設計しました.文字列を先頭ポインタで巡回します.中央に重複文字がある場合は、先頭ポインタと末尾ポインタの間に重複文字がないまで末尾ポインタを移動します.これで私のプログラムは、ヘッダとテールポインタの間の最大距離をリアルタイムで監視するだけでいいです.
コードは次のとおりです.

int lengthOfLongestSubstring(string s)
{
    string::const_iterator head = s.cbegin();
    string::const_iterator tail = s.cbegin();
    std::set<char> dict;
    int count, maxCount = 0;
    while( head != s.cend() )
    {
        if( dict.count(*head) == 0)
        {
            dict.insert(*head);
            count = dict.size();
            maxCount = (count > maxCount) ? count : maxCount;
        }
        else
        {
            while( *tail != *head )
            {
                dict.erase(*tail);
                ++tail;
            }
            ++tail;
        }
        ++head;
    }
    return maxCount;
}

このコードは計算結果は正しいが.しかし、運転速度はやや遅い.実行速度を上げるには、1文字が重複しているかどうかを判別するアルゴリズムを工夫します.よく見られる英字は数文字しかないので、直接ルックアップで処理できます.次に、改良されたコードを示します.運転速度がずいぶん速くなった.

int lengthOfLongestSubstring(string s)
{
    string::const_iterator head = s.cbegin();
    string::const_iterator tail = s.cbegin();
    char dict[128];
    memset(dict, 0, 128);
    int count = 0, maxCount = 0;
    while( head != s.cend() )
    {
        if( dict[*head] == 0)
        {
            dict[*head] = 1;
            ++ count;
            maxCount = (count > maxCount) ? count : maxCount;
        }
        else
        {
            while( *tail != *head )
            {
                dict[*tail] = 0;
                -- count;
                ++tail;
            }
            ++tail;
        }
        ++head;
    }
    return maxCount;
}