let 30 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.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

主题思想: hashMap的运用, 以及滑动窗口,这次学习到了Map的一个新的方法:
Map.getOrDefault(Key key,Value defaultVal);
这个方法,就是获取map中的指定key ,如果没有找到,返回默认val 值,如果找到了就返回key 对应的val 值

解题思路,用一个hashmap 记录下 字符串数组中每个字符串出现的次数,然后对要查找的母串s, 每次查找固定的长度,该长度就是字符串数组L 中所有的字符串长度的和。
在这个固定的长度内,因为字符串L 中每一个字符串的长度是相等的,在依次查找指定长度的字符串,看是否出现在L中过,且出现次数是否相等。

AC 代码:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> ans=new ArrayList<Integer>();
        if(s==null|| words==null|| s.length()<words.length*words[0].length()) return ans;

        Map<String,Integer> wordCount=new HashMap<String,Integer>();
        int perSize=words[0].length();

        for(int i=0;i<words.length;i++)
           wordCount.put(words[i],wordCount.getOrDefault(words[i],0)+1);

        int totalN=s.length();

        Map<String,Integer> checkMap=new HashMap<String,Integer>();
        String tmp;
        for(int i=0;i<=totalN-perSize*words.length;i++){
            checkMap.clear();
            int j=0;
            while(j<words.length){
                 tmp=s.substring(i+j*perSize,i+(j+1)*perSize);
                if(!wordCount.containsKey(tmp)) break;

                checkMap.put(tmp,checkMap.getOrDefault(tmp,0)+1);

                if(checkMap.get(tmp)>wordCount.getOrDefault(tmp,0))break;

                j++;
            }
            if(j==words.length) ans.add(i);

        }
 return ans;
    }

}
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院