首页 > 试题广场 >

找到字符串中的异位词

[编程题]找到字符串中的异位词
  • 热度指数:650 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个字符串 s 和 p ,请你找到 s 子数组中的全部 p 的异位词的起始点。异位词值可以通过重新排列字符顺序(或者不排列)而相等的词。
你可以以任意顺序返回

数据范围: s 和 p 的长度满足 ,字符串中仅包含小写英文字母
示例1

输入

"cabac","abc"

输出

[0,2]
示例2

输入

"ababab","ab"

输出

[0,1,2,3,4]
package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param p string字符串 
 * @return int整型一维数组
*/
func findWord( s string ,  p string ) []int {
    if len(s)<len(p){
        return nil
    }
    cnt1:=map[byte]int{}
    for _,ch:=range []byte(p){
        cnt1[ch]++
    }
    cnt2:=map[byte]int{}
    ans:=[]int{}
    for _,ch:=range []byte(s[:len(p)]){
        cnt2[ch]++
    }
    if check(cnt2,cnt1){
        ans=append(ans,0)
    }
    for l,r:=0,len(p);r<len(s);l,r=l+1,r+1{
        cnt2[s[r]]++
        if cnt2[s[l]]==1{
            delete(cnt2,s[l])
        }else{
            cnt2[s[l]]--
        }
        if check(cnt2,cnt1){
            ans=append(ans,l+1)
        }
    }
    return ans
}

func check(cnt2,cnt1 map[byte]int)bool{
    for k,v:=range cnt2{
        if _,ok:=cnt1[k];!ok{
            return false
        }
        if v!=cnt1[k]{
            return false
        }
    }
    return true
}

发表于 2023-03-16 16:32:45 回复(0)