LeetCode #30. Substring with Concatenation of All Words プログラミング練習

問題：

難易度:　hard
入力:　文字列sと文字列のArray, words
目的: arrayのsubstringの中で、wordsのすべてエレメントの結合があるか判断し、その始まりのindexをリストに格納し返せ
出力:　integer（index）のlist

問題の記述だけ見ると少し分かりにくいかもしれません。
例えば入力の文字列arrayが[one, two, ten]だった場合、
入力文字列sの中に"onetwoten", "onetentwo", "twotenone", "twooneten", "tenonetwo", "tentwoone"のいずれかがあるかを判断し、その始まりのindexをリストに格納し返さなければならない。
sが”onetwotenoneatwoten”の場合、
始まりに最初の文字から始まるonetwotenがwordsの中のすべてのエレメントの組み合わせに該当するので0をlistに置く。
更に3番目から始まるtwotenoneも該当するので3も格納。同じ文字は重複使用可能なのだ。
そのあとのoneatwotenはoneの後ろにwordsの中に存在しない文字が挟んでいるので該当しない。
なので答えは[0, 3]だ。

注意すべき事:　

• wordsの中の文字列達の長さは同じである。

• 任意の組み合わせなので順番はない。

• wordsの中に重複したエレメントがあるテストケースがある。（[good, good]）

以下回答です。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        ArrayList<Integer> res = new ArrayList<>();
        if (words.length == 0 || s.length() == 0) return res;
        int wordlen = words[0].length();
        ArrayList<String> allWords = new ArrayList<>();
        for (String word: words) {
            allWords.add(word);
        }
        for (int i=0; i<s.length(); i++) {
            ArrayList<String> curWords = new ArrayList<>(allWords);
            if (s.length() - i < wordlen * words.length) break;
            int j = i;
            while (true) {
                String newword = s.substring(j, j+wordlen);
                if (curWords.contains(newword)) {
                    curWords.remove(newword);
                    j += wordlen;
                } 
                else {
                    break;
                }
                if (curWords.size() == 0) {
                    res.add(i);
                    break;
                }
            }
        }
        return res;
    }
}

まずwordsのすべてのエレメントを一つのリストに格納する。
wordsのエレメントの長さを記録しwordlenとする。
文字列を最初から読み込み、i+wordlen番目の間のsubstringがリスト内にあるか判断。
ある場合はremoveし続ける。リスト内のすべての要素が取り除かれた場合該当結合文字列なので始まりのindexをresに格納。
該当リスト内にない文字列がある場合はbreakしやり直し。

実はあまりいい回答じゃないらしく、今回のランクはあまり高くありません。
ネット回答の中にHashMapを使った略同じ回答を見つけたのですが2倍くらい早くなっていました。
allWordsにすべての要素と個数を記録し、
curWordsに今の要素と個数を記録していき、equalsした場合記録する方法です。
やはりlistをコピーするのはよくないみたいですね。
もしより良い方法がある方はぜひ教えてください！

今日は以上。
よいプログラミング生活を！