Thinking:

  • Method1: Map, double pointers
    1. 首先我想到的是通过构造所有可能的substring。
    2. 实际上应该先通过创建map存储单词出现的次数，再通过双指针遍历字符串。
	class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s == null || words == null || words.length == 0) return result;
        Map<String, Integer> compare = new HashMap<>();
        int totalLen = 0;
        int maxLen = 0;
        for(String ss : words){
            compare.put(ss, compare.containsKey(ss)?(compare.get(ss) + 1):1);
            totalLen += ss.length();
            maxLen = Math.max(maxLen, ss.length());
        }
        int slow = 0; int fast = 0;int start = 0;
        int len = s.length();
        for(; slow <= len - totalLen; slow ++){
            start = slow;
            fast = start + 1;
            Map<String, Integer> temp = new HashMap<>();
            int count = 0;
            for(; fast <= slow + totalLen && fast <= len; fast++){
                String sub = s.substring(start, fast);
                if(!compare.containsKey(sub)){
                    count ++;
                    if(count == maxLen)
                        break;
                    continue;
                }
                else{
                    count = 0;
                    temp.put(sub, temp.containsKey(sub)?(temp.get(sub) + 1):1);
                    if(temp.equals(compare)){
                        result.add(slow);
                        break;
                    }
                    start = fast;
                }
            }
        }
        return result;
    }
}
  • 好像题目中提出所有的子字符都是等长的 
    class Solution {
  public List<Integer> findSubstring(String s, String[] words) {
      List<Integer> result = new ArrayList<>();
      if(s == null || words == null || words.length == 0) return result;
      Map<String, Integer> compare = new HashMap<>();
      int wordLen = words[0].length();
      int wordNum = words.length;
      for(String ss : words){
          compare.put(ss, compare.containsKey(ss)?(compare.get(ss) + 1):1);
      }
      int slow = 0; int fast = 0;int start = 0;
      int len = s.length();
      for(; slow <= len - wordLen * wordNum; slow++){
          start = slow;
          fast = 1;
          Map<String, Integer> temp = new HashMap<>();
          for(; start + wordLen <= len; fast++ ){
              String sub = s.substring(start, wordLen + start);
              if(!compare.containsKey(sub)){
                  break;
              }
              else{
                  temp.put(sub, temp.containsKey(sub)?(temp.get(sub) + 1):1);
                  if(temp.equals(compare)){
                      result.add(slow);
                      break;
                  }
                  start += wordLen;
              }
          }
      }
      return result;
  }
}