[leetcode]-30-Substring with Concatenation of All Words

ゝ一纸荒年。 2023-07-03 10:40 7阅读 0赞

题目：

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 "barfoo" 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: []

`思路：`

遍历字符串s，每次取出和words一样长的字串，分割成数组subs，比较数组subs和words，若相同（不考虑顺序），则找到一个index放入结果集中。

`代码：`

public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> res = new LinkedList<>();
            if(words == null || words.length == 0) return res;
            int wordLength = words[0].length();
            for(int i = 0; i <= s.length() - wordLength*words.length; ++i){
                String[] subs = new String[words.length];
                int k = i;
                for(int j = 0; j < words.length; ++j) {
                    subs[j] = s.substring(k, k + wordLength);
                    k += wordLength;
                }
                if(compareTwoArrays(subs, words)){
                    res.add(i);
                }
            }
            return res;
        }
        public boolean compareTwoArrays(String[] subs, String[] words){
            HashMap<String, Integer> map = new HashMap<>();
            for(int i = 0; i < words.length; ++i){
                if(map.getOrDefault(words[i], 0) == 0){
                    map.put(words[i],1);
                }else{
                    map.put(words[i], map.get(words[i])+1);
                }
            }
            for(int i = 0; i < subs.length; ++i){
                if(map.getOrDefault(subs[i],0) == 0)
                    return false;
                else
                    map.put(subs[i], map.get(subs[i])-1);
            }
            for(int i = 0; i < words.length; ++i){
                if(map.getOrDefault(words[i], 0) != 0){
                    return false;
                }
            }
            return true;
        }