ikemonn's blog

技術ネタをちょこちょこと

SRM 635 div2 250 IdentifyingWood

Problem Statement

We call a pair of Strings (s, t) "wood" if t is contained in s as a subsequence. (See Notes for a formal definition.)

Given Strings s and t, return the String "Yep, it's wood." (quotes for clarity) if the pair (s, t) is wood and "Nope." otherwise.

書いた

class IdentifyingWood:
    def check(self, s, t):
        if len(t) > len(s):
            return "Nope."
        match_cnt = 0
        s_start = 0
        for t_i in xrange(len(t)):
            for s_i in xrange(s_start, len(s)):
                if t[t_i] == s[s_i]:
                    s_start = s_i + 1
                    match_cnt += 1
                    break
        if match_cnt == len(t):
            return "Yep, it's wood."
        return "Nope."

他の参加者のコード読んだあと

class IdentifyingWood:
    def check(self, s, t):
        is_match = True
        for t_w in t:
            if t_w in s:
                index = s.index(t_w)
                s = s[index+1:]
            else:
                is_match = False
                break
                
        if is_match:
            return "Yep, it's wood."
        return "Nope."

文字列を1つずつ舐めていくのは、 for in で出来るのか。 マッチしたら次からはマッチした文字以降の文字列と比較すれば良いので、indexでマッチした部分を見つけて切っていくのよい。