Leetcode3——Longest Substring Without Repeating Characters

作者:Tyan博客:noahsnail.com  |  CSDN  | 

1.問題の説明

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.

2.解を求める

方法1
i番目の文字を巡回する場合、[index,i-1]の文字の中にs[i]と重複する文字があるかどうかを判断する必要があり、もし文字s[j]とs[i]が重複している場合、indexは直接j+1になり、重複しない文字の数を再計算し、[index,i-1]の文字の中にs[i]と重複する文字がなければ、文字カウントcount++は重複しない.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int count = 0;
        int index = 0;
        //[index,i-1] s[i] 
        boolean flag = false;
        for(int i = 0; i < s.length(); i++) {
            flag = false;
            char ch = s.charAt(i);
            // s[j] s[i] ，index j + 1， 
            for(int j = index; j < i; j++) {
                if(s.charAt(j) == s.charAt(i)) {
                    flag = true;
                    index = j + 1;
                    count = i - j;
                    break;
                }
            }
            if(!flag) {
                count++;
                if(count > max) {
                    max = count;
                }
            }
        }
        return max;
    }
}

方法2の方法2の考え方は,繰返し問題が見られることであり,まずハッシュテーブルを考えると,サブ列を繰り返さないことを解くため,サブ列を2つの部分に分ける必要があり,一部は(i,n−1),一部は(j,i),s[i]が(j,i)にない場合,s[i]をハッシュテーブルに入れ,カウンタに1を加算し,(j,i)にある場合,(j,i)にs[i]と繰り返される文字chを見つけて除去し,もちろん、chを含むサブストリングはs[i]と繰り返し、1文字ずつ削除するたびにj++になるので、ch以前の文字もハッシュテーブルから削除します.iから文字列の最後まで上記の手順を繰り返します.各探しのサブストリングは(j,i)から繰り返されない最長男ストリングである.ここでのjはメソッド1のindexである.考え方と方法の1つは一致しており,違いはハッシュテーブルを用いてループではなく繰り返しを判断することである.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map map = new HashMap();
        int max = 0;
        int count = 0;
        int j = 0;
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // ， ， i 
            if(map.containsKey(ch)) {
                while(map.containsKey(ch)) {
                    map.remove(s.charAt(j));
                    j++;
                    count--;
                }
                count++;
                map.put(ch, ch);
            }else {
                map.put(ch, ch);
                count++;
                if(count > max) {
                    max = count;
                }
            }
        }
        return max;
    }
}

備考:Leetcodeテストの場合、方法は方法より2速度が速いことがわかりました.