Yuyy
Yuyy
LeetCode438. 找到字符串中所有字母异位词

一、思路

这题虽然也是滑动窗口,但是是属于比较“死板”的滑动窗口,因为它的窗口是固定的,所以有相对简单的解法。我将两种解法都写出来了(简单解法和滑动窗口一般解法)。

二、题目

给定一个字符串 和一个非空字符串 p,找到 中所有是 的字母异位词的子串,返回这些子串的起始索引。

字符串只包含小写英文字母,并且字符串 的长度都不超过 20100。

说明:

  • 字母异位词指字母相同,但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

 示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
Related Topics
  • 哈希表
  • \n

  • 👍 457
  • 👎 0
  • 三、代码

    class Solution {
            public List<Integer> findAnagrams(String s, String p) {
                HashMap<Character, Integer> needs = new HashMap<>();
                HashMap<Character, Integer> window = new HashMap<>();
                ArrayList<Integer> ans = new ArrayList<>();
                int valid = 0;
                for (char c :
                        p.toCharArray()) {
                    needs.put(c, needs.getOrDefault(c, 0) + 1);
                }
                for (int i = 0; i < p.length() && i < s.length(); i++) {
                    window.put(s.charAt(i), window.getOrDefault(s.charAt(i), 0) + 1);
                    if (window.get(s.charAt(i)).equals(needs.get(s.charAt(i)))) {
                        valid++;
                    }
                }
                if (valid == needs.size() && valid != 0) {
                    ans.add(0);
                }
                for (int i = 0; i < s.length() - p.length(); i++) {
                    if (needs.containsKey(s.charAt(i))) {
                        if (needs.get(s.charAt(i)).equals(window.get(s.charAt(i)))) {
                            valid--;
                        }
                        window.put(s.charAt(i), window.get(s.charAt(i)) - 1);
                    }
                    char c = s.charAt(i + p.length());
                    if (needs.containsKey(c)) {
                        window.put(c, window.getOrDefault(c, 0) + 1);
                        if (needs.get(c).equals(window.get(c))) {
                            valid++;
                        }
                    }
                    if (valid == needs.size()) {
                        ans.add(i + 1);
                    }
                }
                return ans;
            }
    
            public List<Integer> findAnagrams1(String s, String p) {
                HashMap<Character, Integer> needs = new HashMap<>();
                HashMap<Character, Integer> window = new HashMap<>();
                ArrayList<Integer> ans = new ArrayList<>();
                for (char c :
                        p.toCharArray()) {
                    needs.put(c, needs.getOrDefault(c, 0) + 1);
                }
                int left = 0;
                int right = 0;
                int valid = 0;
                while (right < s.length()) {
                    char c = s.charAt(right++);
                    if (needs.containsKey(c)) {
                        window.put(c, window.getOrDefault(c, 0) + 1);
                        if (needs.get(c).equals(window.get(c))) {
                            valid++;
                        }
                    }
                    while (right - left >= p.length()) {
                        if (valid == needs.size()) {
                            ans.add(left);
                        }
                        char c1 = s.charAt(left++);
                        if (needs.containsKey(c1)) {
                            if (window.get(c1).equals(needs.get(c1))) {
                                valid--;
                            }
                            window.put(c1, window.get(c1) - 1);
                        }
                    }
                }
                return ans;
            }
        }
    
    没有标签
    首页      算法训练      LeetCode438. 找到字符串中所有字母异位词

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode438. 找到字符串中所有字母异位词
    一、思路 这题虽然也是滑动窗口,但是是属于比较“死板”的滑动窗口,因为它的窗口是固定的,所以有相对简单的解法。我将两种解法都写出来了(简单解法和滑动窗口一般解法)。 二、题目 …
    扫描二维码继续阅读
    2021-02-04
    友情链接
    标签
    文章归档
    近期文章