两道Leetcode比赛题 (第140届)

1 二元组匹配

1078. Occurrences After Bigram

要求:输出所有匹配第1、2个单词后的第3个单词

实现思路:

边界判断和1,2单词词对搭配,按正常思路处理即可,无trick和特别的数据结构

python3 代码如下:

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
        if text is None:
            return []
        words = text.split(" ")
        print(words)
        if len(words)<=2:
            return []
        print('here')
        seqs=[]
        seqs = [words[i+2] for i in range(len(words)-2) if words[i] == first and words[i+1] == second]
        return seqs

注意:判断字符相等,选用 == , 注意不要使用 is .

2 字符组合数

1079. Letter Tile Possibilities

返回字符组合数,例如给定:

"AAB",可能的组合如下,返回 8

"A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"

注意:都为大写字母

这道题与Leetcode一些题,同属于一类题目,深度优先搜索 dfs 和回溯相结合,详见:

深度优先搜索和回溯结合后的终极模板

from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        if len(tiles) == 0:
            return 0
        
        dt = dict(Counter(tiles))
        
        return self.dfs(dt);
    
    def dfs(self,dt):
        sum = 0
        for k,v in dt.items():
            if v == 0:
                continue
            
            sum += 1    
            dt[k] -= 1
            sum += self.dfs(dt)
            dt[k] += 1
            
        return sum

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel)

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

原始发表时间:2019-06-16

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券