专栏首页技术面面观边做算法边学go语言之LeetCode1160:拼写单词

边做算法边学go语言之LeetCode1160:拼写单词

前言

本系列文章为《leetcode》刷题笔记。

题目位置:https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters 题集:https://leetcode-cn.com/problemset/all/ 项目位置:https://github.com/pzqu/LeetCode

题目

给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars

假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。

注意:每次拼写时,chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1:

输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释: 
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。

示例 2:

输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。

提示:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100

所有字符串中都仅包含小写英文字母

思路

如上图,这是一题hash table的题目,非常简单,先用一个map统计chars中的字母数量,然后遍历给的字符串数组,逐个统计,对比即可。

统计chars中的字母数量(int类型自动初始化为0

cmap := make(map[uint8]int)

    for i := 0; i < len(chars); i++ {
        cmap[chars[i]] ++
    }

遍历单词集合

for i := 0; i < len(words); i++ {

map拷贝(原理是序列化成json,再反序列化回来)

ExtractInto(cmap, &tmpMap)

遍历单词中的每个字母, 只要没在chars的字典中出现就判断失败,一旦出现就让当前字符字典数量--

j := 0
        for ; j < len(words[i]); j++ {
            if tmpMap[words[i][j]] <= 0 {
                break
            }
            tmpMap[words[i][j]] --
        }

如果j等于了当前单词长度,说明所有字母都包含在里面,就统计上。

if j == len(words[i]) {
            count += len(words[i])
        }

可惜啊。。

估计是map本身寻找hash位置耗时,以及map拷贝耗时优化一下代码,把map转换成数组。

长度为26个字母,下标就是0-25,也就是a-az-a

详细代码如下一节优化后。

代码

优化前 Go

func countCharacters(words []string, chars string) int {
    cmap := make(map[uint8]int)

    for i := 0; i < len(chars); i++ {
        cmap[chars[i]] ++
    }

    count := 0
    tmpMap := make(map[uint8]int)

    for i := 0; i < len(words); i++ {
        ExtractInto(cmap, &tmpMap)
        j := 0
        for ; j < len(words[i]); j++ {
            if tmpMap[words[i][j]] <= 0 {
                break
            }
            tmpMap[words[i][j]] --
        }
        if j == len(words[i]) {
            count += len(words[i])
        }
    }

    return count
}

/*
    把interface类型转换成我们想要的struct类型
    这个通用方法可以转换成任意一个想要的类型
 */
func ExtractInto(source interface{}, to interface{}) error {
    b, err := json.Marshal(source)
    if err != nil {
        return err
    }
    err = json.Unmarshal(b, to)
    return err
}

优化后 Go

//优化后
func countCharacters(words []string, chars string) int {
    var byteCount [26]int
    for _, char := range chars {
        byteCount[char-'a']++
    }

    ret := 0
    for _, word := range words {
        bc, match := byteCount, true
        for _, char := range word {
            if bc[char-'a'] <= 0 {
                match = false
                break
            }
            bc[char-'a']--
        }
        if match {
            ret += len(word)
        }
    }
    return ret
}

本文分享自微信公众号 - 编程三分钟(coding3min),作者:做算法的小熊

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 三分钟学 Go 语言——range深度解析

    小熊最近两天加班比较严重,要处理的事情很多,但是学习的热情永远不会减少,前面讲述的go语言语法是非常非常简单的,所以没有做深入的剖析,后面会从各种角度解析语法,...

    机智的程序员小熊
  • 让你的Golang项目在IDE里跑起来(Goland使用入门-GOROOT、GOPATH、src、 pkg、bin...)

    每次新建项目,不熟悉go的项目结构,一般跑都跑不起来,每次都要重新搞一遍,好几回跑项目都会报类似File is invalid的错误

    机智的程序员小熊
  • 三分钟学 Go 语言——函数深度解析(下) 可变参数

    小熊这两天因为个人种种令人难受的原因,没有能更新,也没有提前请假,给大家道歉歉了。

    机智的程序员小熊
  • 持久化储存(一)

    https://yeasy.gitbooks.io/docker_practice/install/mac.html

    一粒小麦
  • android MVVM开发模式(五)

    android MVVM开发模式(五) 上一讲我们说了@InverseBindingAdapter标记的事情。通过这个,我们可以实现view向数据方向的传递。从...

    用户1263308
  • 「docker实战篇」python的docker爬虫技术-mitmproxy之安卓模拟器如何抓包(十)

    PS:基本的mitmproxy的使用就讲到这里,拦截什么的还是比较好用的。基本每个抓包工具都有自己的共同点拦截,改包功能。

    IT故事会
  • 当creator遇上protobufjs|激情

    我们上一篇讲解了通过修改源码的方案,让protobufjs能正常运行在jsb环境上。这个方案适合将protobufjs源码直接放到项目中,而我们使用npm来管理...

    张晓衡
  • Android App漏洞学习(二)

    接上一篇没写完的文章《Android App漏洞学习(一)》,下面继续剩下的几个部分。

    信安之路
  • leetcode: 68. Text Justification [✗]

    JNingWei
  • 将被自然语言处理和文字分析颠覆的行业:法律,保险和客服

    大数据文摘

扫码关注云+社区

领取腾讯云代金券