8.15 - hard - 53

291. Word Pattern II

又是一道backtracking的題目瘦癌,修修補(bǔ)補(bǔ)也算是AC了

class Solution(object):
    def wordPatternMatch(self, pattern, s):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        m = {}
        for c in pattern:
            if c not in m:
                m[c] = ""
        return self.dfs(pattern, s, m, 0, 0)
    
    def dfs(self, pattern, s, m, p, pos):
        if pos == len(s) and p == len(pattern):
            return True
        if pos == len(s):
            return False
        if p == len(pattern):
            return False
        
        for i in range(pos, len(s)):
            cur = s[pos:i+1]
            cur_key = None
            for key, value in m.iteritems():
                if value == cur:
                    cur_key = key
            if cur_key and cur_key != pattern[p]:
                continue
            if m[pattern[p]]:
                if m[pattern[p]] == cur:
                    if self.dfs(pattern, s, m, p+1, i+1):
                        return True
            else:
                m[pattern[p]] = cur
                if self.dfs(pattern, s, m, p+1, i+1):
                    return True
                m[pattern[p]] = ""
        return False
          
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末官边,一起剝皮案震驚了整個濱河市裸删,隨后出現(xiàn)的幾起案子冷蚂,更是在濱河造成了極大的恐慌,老刑警劉巖诽偷,帶你破解...
    沈念sama閱讀 212,599評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件锋边,死亡現(xiàn)場離奇詭異,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)僧凤,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,629評論 3 385
  • 文/潘曉璐 我一進(jìn)店門畜侦,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人躯保,你說我怎么就攤上這事旋膳。” “怎么了途事?”我有些...
    開封第一講書人閱讀 158,084評論 0 348
  • 文/不壞的土叔 我叫張陵验懊,是天一觀的道長。 經(jīng)常有香客問我尸变,道長义图,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,708評論 1 284
  • 正文 為了忘掉前任召烂,我火速辦了婚禮碱工,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘奏夫。我一直安慰自己怕篷,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 65,813評論 6 386
  • 文/花漫 我一把揭開白布酗昼。 她就那樣靜靜地躺著廊谓,像睡著了一般。 火紅的嫁衣襯著肌膚如雪麻削。 梳的紋絲不亂的頭發(fā)上蹂析,一...
    開封第一講書人閱讀 50,021評論 1 291
  • 那天,我揣著相機(jī)與錄音碟婆,去河邊找鬼电抚。 笑死,一個胖子當(dāng)著我的面吹牛竖共,可吹牛的內(nèi)容都是我干的蝙叛。 我是一名探鬼主播,決...
    沈念sama閱讀 39,120評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼公给,長吁一口氣:“原來是場噩夢啊……” “哼借帘!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起淌铐,我...
    開封第一講書人閱讀 37,866評論 0 268
  • 序言:老撾萬榮一對情侶失蹤肺然,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后腿准,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體际起,經(jīng)...
    沈念sama閱讀 44,308評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡拾碌,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,633評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了街望。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片校翔。...
    茶點故事閱讀 38,768評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖灾前,靈堂內(nèi)的尸體忽然破棺而出防症,到底是詐尸還是另有隱情,我是刑警寧澤哎甲,帶...
    沈念sama閱讀 34,461評論 4 333
  • 正文 年R本政府宣布蔫敲,位于F島的核電站,受9級特大地震影響炭玫,放射性物質(zhì)發(fā)生泄漏燕偶。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 40,094評論 3 317
  • 文/蒙蒙 一础嫡、第九天 我趴在偏房一處隱蔽的房頂上張望指么。 院中可真熱鬧,春花似錦榴鼎、人聲如沸伯诬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,850評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽盗似。三九已至,卻和暖如春平项,著一層夾襖步出監(jiān)牢的瞬間赫舒,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,082評論 1 267
  • 我被黑心中介騙來泰國打工闽瓢, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留接癌,地道東北人。 一個月前我還...
    沈念sama閱讀 46,571評論 2 362
  • 正文 我出身青樓扣讼,卻偏偏與公主長得像缺猛,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子椭符,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,666評論 2 350

推薦閱讀更多精彩內(nèi)容