leetcode438 找到字符串中所有字母异位词

文章目录

简介

其实我的算法并不是强项,然后今天在做438这道题的时候发现了一个让我无比佩服的思路,这里记录一下和大家分享:
首先看一下题目:
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

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

说明:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

我的思路

首先说说我的思路(时间没过,没兴趣的可以跳过,直接看大神解法)

  • 用hashMap存储p的每个单词的个数
    * left <- 0 right <- 0 这是滑动窗口的左右标记
    * list res 结果的列表
    * while (right < s.len){
    * if (marker == 0){ //marker用来标记现在还有几个没找到
    * res.append(left)
    * charAt(left)的hashmap value++;
    * 恢复marker
    * }else{
    * right++;
    * check hashmap(charAt(right)) 如果小于0,{
    * 遍历left++ 直到left = right的ch;更新left。continue
    * }else{
    * hashMap --;
    * if hashMap ==0 将bitmap相应位置0
    * }
    * }
    * }

代码:

public List<Integer> findAnagrams1(String s, String p) {
        Map<Integer, Integer> charMap = new HashMap<Integer, Integer>();
        Map<Integer, Integer> bitMap = new HashMap<Integer, Integer>();
        List<Integer> res = new ArrayList<Integer>();
        int marker = 0;
        int left = 0, right = -1;
        for (int i = 0; i < p.length(); i++) {
            int ch = p.charAt(i);
            if (charMap.containsKey(ch)) {
                charMap.put(ch, charMap.get(ch) + 1);
            } else {
                charMap.put(ch, 1);
            }
        }
        bitMap.putAll(charMap);
        int marker_=p.length();
        marker = p.length();

        while (right < s.length()) {
            if (marker == 0) {
                res.add(left);
                left = left + 1;
                right = left - 1;
                marker = marker_;
                charMap.clear();
                charMap.putAll(bitMap);
//                int mark = s.charAt(left);
//                charMap.put(mark, charMap.get(mark) - 1);
//                marker++;
            } else {
                if (right + 1 < s.length()) {
                    right++;
                }else{
                    break;
                }
                if (!charMap.containsKey(Integer.valueOf(s.charAt(right)))) {
                    left = right + 1;
                    marker = marker_;
                    charMap.clear();
                    charMap.putAll(bitMap);
                } else {
                    if (charMap.get(Integer.valueOf(s.charAt(right))) == 0) {
                        while (left <= right) {
                            int tmp = s.charAt(left);
                            if (tmp == Integer.valueOf(s.charAt(right))) {
                                left++;
                                break;
                            } else {
                                charMap.put(tmp, charMap.get(tmp) + 1);
                                marker++;
                                left++;
                            }
                        }
                    } else {
                        int tmp = s.charAt(right);
                        charMap.put(tmp, charMap.get(tmp) - 1);
                        marker--;
                    }
                }
            }
        }
        return res;
    }

其实我自己在写的时候就觉得有些冗杂和烦琐了,当然我一般还会花时间去优化一下,但也是因为这次比较着急,直接看到了大神的解法,让我自己琢磨和学习了很久。

大神解法

直接上代码:

public List<Integer> findAnagrams(String s, String p) {
        int slength = s.length();
        int plength = p.length();
        int conter = 0;
        StringBuilder sb = new StringBuilder(p);
        List<Integer> result = new ArrayList();
        for(int i=0; i<slength; i++)
        {
            if(sb.indexOf(Character.toString(s.charAt(i))) != -1)
            {
                conter++;
                sb.delete(sb.indexOf(Character.toString(s.charAt(i))), sb.indexOf(Character.toString(s.charAt(i)))+1);
            }
            else
            {
                if(p.indexOf(Character.toString(s.charAt(i))) != -1)
                {
                    conter--;
                    i--;
                    sb.append(s.charAt(i-conter));
                }
                else
                {
                    conter = 0;
                    sb =  new StringBuilder(p);
                }
            }


            if(conter == plength)
            {
                result.add(i-plength+1);
                conter--;
                sb.append(s.charAt(i-plength+1));
            }
        }
        return result;
    }

这里其实没有它的思路,然后我自己研究了一下,这里做一下总结。

首先,我得说,是我自己陷入了固定的滑动窗口解体的套路当中,当然对于一些题目来说,滑动窗口是非常有效率的,但是不应该只是知道了滑动窗口就限制了自己的思路。

  • 变量的声明方面:

作者声明了
int slength = s.length();
int plength = p.length();
int conter = 0;
StringBuilder sb = new StringBuilder§;
List result = new ArrayList();

前两个不用多说了,分别是长度。然后conter是记录的当前已经扫描到了几个属于p串的字符。定义p的sb是为了记录当前已经有哪些字符已经在s中找到了,找到了就把把它从sb中删掉,那么剩下的就是还没有匹配到的。
result就是记录结果了。

  • 流程逻辑
for ch in str.s {
	if ch in sb:   sb.delete(ch)  同时conter计数+1
	else(也就是说不在sb串中的ch){
		首先判断在不在p中
		if 在p中: 将ch的索引i回退,conter--,将(i-conter)元素增加到sb。
		//这里其实我也困惑了一会,后来发现这里才是精彩的地方,当面对这种情况的时候,
		//其实是已经找到了足够数量的某个字母char0,但是又遇到了一个char0,这个字母现在多了,
		//那么怎么样才能继续走下去呢,就需要将前面的已经遇到的第一个char0找到,从index(char0)+1开始,
		//重新计算。所以这里就是首先将i--,表示重新扫描,并且将conter--,用i-conter来找到当前
		//的最左面的第一个字母charLeft,增加到sb,就是说又需要这个charLeft了。
		else (也不在p中) 说明这个字母肯定不对了,只能舍弃重新开始扫描。 所以初始化变量 :conter=0 sb = (p)

		if conter == plength:
			符合条件,记录res;
	}
}

总结

  • 使用StringBuilder,避免使用str加法。
  • 使用隐式的滑动窗口才是真正滑动窗口方法的精髓,不一定需要left和right的交替移动,心中有window才是高级的算法。

大家共勉~~

leetcode438 找到字符串中所有字母异位词leetcode438 找到字符串中所有字母异位词 Braylon1002 发布了51 篇原创文章 · 获赞 55 · 访问量 8960 私信 关注
上一篇:面试题九宫格输入法,数字和字符串转换


下一篇:设计模式之策略模式