LeetCode 1160. 拼写单词 Find Words T

作者: 1江春水 | 来源:发表于2019-08-26 18:01 被阅读0次

    【题目描述】
    给你一份『词汇表』(字符串数组) 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、1 <= words.length <= 1000
    2、1 <= words[i].length, chars.length <= 100
    3、所有字符串中都仅包含小写英文字母
    

    【思路】
    1、字符个数比较,使用哈希表
    2、words中的每个单词和chars比较,chars包含单词 单词的个数记录下来,否则下一个单词
    3、时间复杂度0(m*n) m为单词的个数 n为单词的字符数
    4、空间复杂度O(n)

    Swift代码实现:

    func countCharacters(_ words: [String], _ chars: String) -> Int {
        if chars.count == 0 || words.count == 0 { return 0 }
        var charsMap = [Character:Int]()
        for c in chars {
            var value = charsMap[c] ?? 0
            value+=1
            charsMap[c] = value
        }
        var strArr = [String]()
        for str in words {
            var tmp = charsMap
            for (i,cc) in str.enumerated() {
                var count = tmp[cc] ?? 0
                if count == 0 {
                    break
                }
                count-=1
                tmp[cc] = count
                if i == str.count-1 {
                    strArr.append(str)
                }
            }
        }
        var res = 0
        for s in strArr {
            res+=s.count
        }
        return res
    }
    

    相关文章

      网友评论

        本文标题:LeetCode 1160. 拼写单词 Find Words T

        本文链接:https://www.haomeiwen.com/subject/eevdectx.html