LeetCode 438. Find All Anagrams in a String （在字符串中找到所有的变位词）-白红宇

LeetCode 438. Find All Anagrams in a String （在字符串中找到所有的变位词）

阅读量：5083 次

发布时间：2019-06-13

本文共 2238 字，大约阅读时间需要 7 分钟。

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:s: "cbaebabacd" p: "abc"Output:[0, 6]Explanation:The substring with start index = 0 is "cba", which is an anagram of "abc".The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:s: "abab" p: "ab"Output:[0, 1, 2]Explanation:The substring with start index = 0 is "ab", which is an anagram of "ab".The substring with start index = 1 is "ba", which is an anagram of "ab".The substring with start index = 2 is "ab", which is an anagram of "ab".

题目标签：Hash Table

　　题目给了我们两个string s 和 p，让我们在 s 中找到所有 p 的变位词。

　　利用两个HashMap 和 Sliding window：

　　　　先把 p 的char 和出现次数存入 mapP；

　　　　然后遍历string s，利用 sliding window 把和 p 一样长度的 string 的 char 保存在 tempMap 里，比较 tempMap 和 mapP。

Java Solution:

Runtime beats 20.00%

完成日期：11/07/2017

关键词：HashMap

关键点：利用sliding window 把 tempMap 和 mapP 比较

1 class Solution  2 { 3     public List
      
        findAnagrams(String s, String p)  4     { 5         List
       
         list = new ArrayList<>(); 6         HashMap
        
          mapP = new HashMap<>(); 7         HashMap
         
           tempMap = new HashMap<>(); 8          9         for(char c: p.toCharArray()) // store p char and occurrence into mapP10             mapP.put(c, mapP.getOrDefault(c, 0) + 1);11         12         13         for(int i=0; i
          
           = p.length()) // once reach to p's length, remove most left char21             {22                 leftC = s.charAt(i - p.length());23                 // remove left char24                 if(tempMap.get(leftC) == 1)25                     tempMap.remove(leftC);26                 else27                     tempMap.put(leftC, tempMap.get(leftC) - 1);28             }29             30             if(tempMap.equals(mapP))31                 list.add(i + 1 - p.length());32          33             34         }35             36         return list;37     }38 }