首页 > 代码库 > [Leetcode] DP-- 467. Unique Substrings in Wraparound String
[Leetcode] DP-- 467. Unique Substrings in Wraparound String
Consider the string s
to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s
will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Now we have another string p
. Your job is to find out how many unique non-empty substrings of p
are present in s
. In particular, your input is the string p
and you need to output the number of different non-empty substrings of p
in the string s
.
Note: p
consists of only lowercase English letters and the size of p might be over 10000.
Example 1:
Input: "a" Output: 1 Explanation: Only the substring "a" of string "a" is in the string s.
Example 2:
Input: "cac" Output: 2 Explanation: There are two substrings "a", "c" of string "cac" in the string s.
Example 3:
Input: "zab" Output: 6 Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.
Solution:
1. naive method to get all the substring from p and judge whether it is in the wrapround string
2. use DP
for naive method, there are lots of repetition
1) for string p: "abcd"
a => ends with "a", there are total 1 here
ab => ends with b, there are "ab", "b", total 2
abc => ends with c, there are "abc", "bc" , "c", total 3
abcd =>ends with d, there are "abcd", "bcd", "cd", "d" , total 4
the answer of the substring is 1+2+3+4
so the number of unique substirng of p in s is for every letter in p which has the maximum unique continuous substring end in each character and then sum,
but it needs to get rid of the duplicated one
2) if string p : "abcdabc"
the latter "abc" will be duplicated for ending character a, b, c.
therefore, we need to get the maximum of number of substring in same ending character.
3) if string p: ade
ad is not continous substring, so the maximum of number of substring ending in "d" will be 1 again
1 if p is None or len(p) == 0: 2 return 0 3 dp= [0] * 26 # 26 letters 4 maxCnt = 0 5 6 for i in range(0, len(p)): 7 if i > 0 and (ord(p[i]) - ord(p[i-1]) == 1 or ord(p[i-1]) - ord(p[i]) == 25): 8 maxCnt += 1 9 else: 10 maxCnt = 1 11 index = ord(p[i]) - 97 12 13 dp[index] = max(dp[index], maxCnt) 14 15 #print ("directly: ", p[i], dp[index]) 16 17 ans = 0 18 for ele in dp: 19 ans += ele 20 return ans 21
[Leetcode] DP-- 467. Unique Substrings in Wraparound String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。