Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
将一列字符串切分成若干子串,要求每个子串转为十进制数的数值位于[1, k],问一共多少种切分方法,DP


 1 #1416
 2 #Runtime: 1325 ms (Beats 100%)
 3 #Memory: 20 MB (Beats 25%)
 4 
 5 class Solution(object):
 6     def numberOfArrays(self, s, k):
 7         """
 8         :type s: str
 9         :type k: int
10         :rtype: int
11         """
12         MOD = 10**9+7
13         n = len(s)
14         dp = [0] * (n + 1)
15         dp[n] = 1
16         for i in range(n - 1, -1, -1):
17             if s[i] == '0':
18                 continue
19             t = 0
20             j = i + 1
21             while j <= n and int(s[i : j]) <= k:
22                 t += dp[j]
23                 j += 1
24             dp[i] = t % MOD
25         return dp[0]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理