美文网首页
8.22 - hard - 81

8.22 - hard - 81

作者: 健时总向乱中忙 | 来源:发表于2017-08-22 23:27 被阅读0次

411. Minimum Unique Word Abbreviation

利用比较基本的方法,backtracking找出全部的abbreviation,TLE

class Solution(object):
    def minAbbreviation(self, target, dictionary):
        """
        :type target: str
        :type dictionary: List[str]
        :rtype: str
        """
        # 基本想法是先把dict里的所有可能的变形都找出来
        # 然后再找target
        res = set()
        if dictionary:
            for word in dictionary:
                self.search(word, "", 0, 0, res)
        if not res:
            return str(len(target))
        target_set = set()
        self.search(target, "", 0, 0, target_set)
        new = target_set.difference(res)
        
        return sorted(new, key=self.cal)[0]
        
        
    def cal(self, s):
        l = 0
        first_digit = True
        for c in s:
            if first_digit and c.isdigit():
                l += 1
                first_digit = False
            if not c.isdigit():
                l += 1
                first_digit = True
        
        return l
        
    
    def search(self, s, cur, pos, count, res):
        if pos == len(s):
            if count > 0:
                cur += str(count)
            res.add(cur)
            return
        
        self.search(s, cur, pos+1, count+1, res) # 缩略当前的字母增加count
        if count > 0:
            cur = cur + str(count) + s[pos]
        else:
            cur = cur + s[pos]
        self.search(s, cur, pos+1, 0, res)

相关文章

  • 8.22 - hard - 81

    411. Minimum Unique Word Abbreviation 利用比较基本的方法,backtrack...

  • 8.22 - hard - 85

    440. K-th Smallest in Lexicographical Order 和之前有一道386. Le...

  • 8.22 - hard - 86

    446. Arithmetic Slices II - Subsequence 一道dp的题目

  • 8.22 - hard - 87

    460. LFU Cache 有点做不动了。。。基本思想是。。。(这题要重看,先休息一会)

  • 8.22 - hard - 90

    471. Encode String with Shortest Length 一道对角线型dp题目,对角线是我自...

  • 8.22 - hard - 88

    465. Optimal Account Balancing 这道题挺有意思的,用greedy的方法

  • 8.22 - hard - 89

    466. Count The Repetitions这题好困难,看了答案也很难理解,估计只能背答案了。。。等复习的...

  • 8.22 - hard - 83

    425. Word Squares 利用Trie和backtracking来做。利用trie来找prefix

  • 8.22 - hard - 84

    432. All O`one Data Structure 基本的想法就是利用一个双向链表来维持单调性,每个nod...

  • 8.22 - hard - 82

    420. Strong Password Checker 这道题要分成几种情况做When len > 20, we...

网友评论

      本文标题:8.22 - hard - 81

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