找出字母异位词

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

题目描述

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

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

说明

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。
• 最后输出一个List类实例即可

样例输入输出:

示例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" 的字母异位词。

1.1. 直观解法

1. 逐个切片
2. 比较切片与待匹配字串
   • 无序则放入数组排序后逐个比较
   • 无序或者使用键值对记住每个字母顺序

import java.util.*;
// 所谓的切片就是kmp暴力版本啊
public class Test{
    public static String match(String s,String p){
        // 切片
        int lengthA = s.length(); int lengthB = p.length();
        if(lengthA<lengthB || s==null | p==null) return "None";
        String list="";
 
        HashMap<Character,Integer> p_map = new HashMap<>();
        for(int i = 0; i < lengthB;i++){
            char c = p.charAt(i);
            int count = p_map.getOrDefault(c, 0);
            if(p_map.containsKey(c)){
                count++;
            }
            p_map.put(c, count);
        }
        
        for(int i = 0; i <(lengthA-lengthB+1);i++){
            // 随着每次循环的结束,s_cut这个引用被销毁然后它再被声明创建
            String s_cut = s.substring(i,i+lengthB);
        // 切片之后与p进行比较
        // 比较之前需要将p与切片都变成有序的
            HashMap<Character,Integer> s_cut_map = new HashMap<>();
            for(int j = 0; j < lengthB;j++){
                char c = s_cut.charAt(j);
                int count = s_cut_map.getOrDefault(c, 0);
                if(s_cut_map.containsKey(c)){
                    count++;
                }
                s_cut_map.put(c, count);
            }
            if(p_map.equals(s_cut_map))
                list = list+i+" ";
            
        }
        if(list!="") return list;
        else return "None";
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String s= input.nextLine();
        String p = input.nextLine();
        System.out.println(match(s, p));
        input.close();
    }
}

1.2. 巧妙解法

巧妙的解法此时因为难以理解不被你喜欢