首页 > 编程学习 > 每日一题|2022-11-8|1684. 统计一致字符串的数目|哈希表|Golang

1684. 统计一致字符串的数目

        思路1:丢人做法

        哈希记录allowed,暴力遍历words所有字母,如果有不在哈希表里的,计数。最后用words的长度减去 计数 就行。

func countConsistentStrings(allowed string, words []string) int {
    has1 := make(map[rune]int)
    for _, v := range allowed {
        has1[v]++
    }
    sub := 0
    for _, v1 := range words {
        for _, v2 := range v1 {
            _, ok := has1[v2] 
            if !ok {
                sub++
                break
            }
        }
    }
    return len(words) - sub 
}

思路2:位运算做法

func countConsistentStrings(allowed string, words []string) int {
    // 由于allowed全是小写字母,可以用一个int存放其对应的二进制位,例如a为00000000 00000000 0000000 00000001, b存在第二位,以此类推
    maskA := 0
    for _, v := range allowed {
        maskA |= 1 << (v-'a')
    }

    // 遍历words中的每个字符串,
    ans := 0
    for _, word := range words {
        maskB := 0 
        for _, v := range word {
            maskB  |= 1 << (v - 'a')
        }
        if maskA | maskB == maskA  {
            ans++
        }
        /*
            allowed  =  ab = 11 
            words[0] = ad = 1001
            allowed | words[0]  = 1011 != 11

            allowed =  ab = 11
            words[1] = bd = 0101
            allowed | words[1]  =  0111 != 11 

            allowed = ab = 11
            words[2] = aaab =  11
            allwoed | words[2] = 11 == 11 
            ans++
        */
    }
    return ans
}
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式