LeetCodeWeekly 239B 1849. Splitting a String Into Descending Consecutive Values 連続する減少数列の結合の判定

前日のGCJ-Bに近いものを感じます．

題意

• 最大２０桁の数字が与えられる
• その数字がa, a-1, ... a-nの数字を連結して作られた文字列かを判定しろ
• ただし、各数字の頭には0がついていても良い

こう考えた

まず、この問題の難しさは3つめの「頭に0が付いていても良い」というところで、例えば、5,4,3という数字を組み合わせた時に、$543$は当然として、$5043$や$50004$や$54003$なども候補となるからである．

もしも、あたまの0を気にしなくて良いのであれば、適当にi文字までをとった時にデクリメントしながら数字を生成して判定すれば良いがそうもいかない．

このため、以下のような関数f$(s, num)$を考える．

• 前の数字が$num$とする時に、$s$自身が$num-1$、あるいは、$num-1$を払い出せる
• $num-1$を払い出したのであれば、$f(残りの文字列, num-1)$が成立するかを調べる．

実装

上記をそのまま実装すればいい．つまり、

• 最初はi文字目までを必ずカットする
• i文字目までをカットした時、$num-1$に作れるカットがあるなら再起的に追う

class Solution:
    def f(self,s, num):
        if num is not None and int(s) == (num - 1):
            return True
        for i in range(1, len(s)):
            curval = s[:i]
            if num is not None and int(curval) != (num-1):
                continue
            res = self.f(s[i:], int(curval))
            if res is True:
                return True
        return False
    def splitString(self, s: str) -> bool:
        return self.f(s, None)