Time limit exceed


  • 2
    S
    public class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> result = new ArrayList<Integer>();
            if (words == null || words.length == 0) {
                return result;
            }
            
            HashMap<String, Integer> wordLeft = new HashMap<String, Integer>();
            HashMap<String, Integer> wordFind = new HashMap<String, Integer>();
            
            for (String word : words) {
                if (!wordLeft.containsKey(word)) {
                    wordLeft.put(word, 1);
                }
                else {
                    wordLeft.put(word, wordLeft.get(word) + 1);
                }
            }
            
            int nWords = words.length, wordLength = words[0].length();
            for (int i = 0; i <= s.length() - nWords*wordLength; i++) {
                wordFind.clear();
                int j = 0;
                for (j = 0; j < nWords; j++) {
                    String sub = s.substring(i + j*wordLength, i + (j + 1)*wordLength);
                    if (!wordLeft.containsKey(sub)) break;
                    
                    if (!wordFind.containsKey(sub)) {
                        wordFind.put(sub,1);
                    }
                    else {
                        wordFind.put(sub, wordFind.get(sub) + 1);
                    }
                    
                    if (wordFind.get(sub) > wordLeft.get(sub)) break;
                }
                
                if (j == nWords) result.add(i);
            }
            
            return result;
        }
    }

Log in to reply
 

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