LeetCodeWeekly 239B 1849. Splitting a String Into Descending Consecutive Values 連続する減少数列の結合の判定
前日のGCJ-Bに近いものを感じます.
題意
- 最大20桁の数字が与えられる
- その数字が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)
Author And Source
この問題について(LeetCodeWeekly 239B 1849. Splitting a String Into Descending Consecutive Values 連続する減少数列の結合の判定), 我々は、より多くの情報をここで見つけました https://qiita.com/recuraki/items/5f80233b83e2b39d058f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .