Java O(n) solution when consider substring() as O(1)


  • 5
    L

    Maybe this is the so called window technique. The window was moved right by the while(){} loop. Since substring() is actually expensive in Java, each time I store the substring in a variable to avoid repeatedly calling the substring() function.

    More specifically, there are three cases that the window changes:

    1.The substring at the right of the window is not in words dictionary, then we move the whole window to the right side of this substring and set the window back to an empty window.

    2.The substring at the right of window is a candidate word and not used out by the current window, then we add this substring into window. The window's right boundary extends. Now if the window is a valid solution, add the start index of window to result and cut off the head word of the window for further checking, the window's left boundary shrinks.

    3.The substring at the right of window is a candidate word and is used out by the current window. Then we cut off the head word of the window, the window's left boundary shrinks (This would be done repeatedly by the while loop until the substring is not used out by the current window and could be added into the window).

    public class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> res = new ArrayList<Integer>();
            if(words.length==0||words[0].length()==0) return res;
            Map<String,Integer> wordDict = new HashMap<String,Integer>();
            for(String word : words) {
                if(!wordDict.containsKey(word)) wordDict.put(word,1);
                else wordDict.put(word,wordDict.get(word) + 1);
            }
            Map<String,Integer> currWords = new HashMap<String,Integer>();
            int len = words[0].length();
            for(int i = 0; i < len; i++) {
                int k = i, j = i; //k is at the head of the window and j is the last.
                int addedCount = 0; //to indicate whether we add index to res.
                while(k<= s.length()-len*words.length&&j + len <= s.length()) { //make sure the remaining length is enough.
                    String subWord = s.substring(j,j+len);
                    if(!wordDict.containsKey(subWord)) { //the substring is not in words, head jumps to the right of this substring.
                        addedCount = 0;
                        currWords.clear();
                        j += len;
                        k = j;
                        continue;
                    }
                    if(!currWords.containsKey(subWord)||currWords.get(subWord)!=wordDict.get(subWord)) {
                        if(!currWords.containsKey(subWord)) currWords.put(subWord,1);
                        else currWords.put(subWord,currWords.get(subWord) + 1); //update the current words we used.
                        addedCount++;
                        if(addedCount == words.length) { //if get a index, add it to res. And we need to continue checking
                            res.add(k);
                            addedCount--; //remove the head and check new substring, so count-- and move head to new position.
                            String preHead = s.substring(k,k+len);
                            if(currWords.get(preHead)==1) currWords.remove(preHead); //update the currWords map.
                            else currWords.put(preHead,currWords.get(preHead)-1);
                            k += len;
                        }
                        j += len;
                    }
                    else { //the current substring was used out before. Move head len steps right.
                        String preHead = s.substring(k,k+len);
                        addedCount--;
                        if(currWords.get(preHead)==1) currWords.remove(preHead); //update the currWords map.
                        else currWords.put(preHead,currWords.get(preHead)-1);
                        k += len; //don't move j this case.
                    }
                }
                currWords.clear();
            }
            return res;
        }
    }'

  • 0
    I

    Thank you for your answer, logically readable!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.