30. Substring with Concatenation of All Words (Hard)

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solutions

class Solution {

    // This problem should not be classified as hard.

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new LinkedList<>();

        if (s == null || s.length() == 0 || words.length == 0) {
            return ans;
        }

        // length of each word
        int wordLen = words[0].length();

        // length of the combination of all the words
        int combLen = wordLen * words.length;

        // Combination string should not be longer than given s
        if (s.length() < combLen) {
            return ans;
        }

        // Keep the word frequency in words
        Map<String, Integer> wordsFreqMap = new HashMap<>();

        // Initialization
        for (int i = 0; i < words.length; i++) {
            if (!wordsFreqMap.containsKey(words[i])) {
                wordsFreqMap.put(words[i], 0);
            }

            wordsFreqMap.put(words[i], wordsFreqMap.get(words[i]) + 1);
        }

        for (int i = 0; i <= s.length() - combLen; i++) {

            boolean matched = true;

            // Keep the frequency of matched words in s
            Map<String, Integer> matchedFreqMap = new HashMap<>();

            String ss = s.substring(i, i + combLen);
            for (int j = 0; j < words.length; j++) {
                String sss = ss.substring(j * wordLen, (j + 1) * wordLen);
                if (!matchedFreqMap.containsKey(sss)) {
                    matchedFreqMap.put(sss, 0);
                }

                matchedFreqMap.put(sss, matchedFreqMap.get(sss) + 1);

                // if word sss does not exist in the dictionary or its frequency larger than required, we take it unmatched.
                if (!wordsFreqMap.containsKey(sss) || matchedFreqMap.get(sss) > wordsFreqMap.get(sss)) {
                    matched = false;
                    break;
                }
            }

            if (matched) {
                ans.add(i);
            }
        }

        return ans;
    }
}

Incorrect Solutions

References

  1. https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13816/My-solution-in-JAVA-seeking-advice-for-improvement
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-27 14:34:34

results matching ""

    No results matching ""