-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path467.py
More file actions
111 lines (90 loc) · 2.85 KB
/
467.py
File metadata and controls
111 lines (90 loc) · 2.85 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
'''
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.
False Trial:
1. subproblems
- the next non-consecutive character i0...ik,
2. guessing a possible solution
- G(ik) = sum[ik - i0, ..., 1]
- G(p) = sum(G(i))
3. recurrences:
- G(p) = sum(sum(ik - i0,...1))
4. time: O(n * S) S is the length of each possible substring of s
Correct Sol:
1. subproblems:
- unique substring ending with 'a', 'b', 'c',...'z'
2. guess a sol:
- F('a') = len(unique substring) - 1
- Count(n) = F('a') + F('b') +...+F('z')
'''
class Solution(object):
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
dp = [0] * 26
length_at_chr = 0
for i in range(len(p)):
if (i > 0 and (ord(p[i]) - ord(p[i - 1]) == 1
or abs(ord(p[i]) - ord(p[i - 1])) == 25)):
length_at_chr += 1
else:
length_at_chr = 1
index = ord(p[i]) - ord('a')
if length_at_chr > dp[index]:
dp[index] = length_at_chr
#print(dp)
return sum(dp)
# G = [0] * (len(p) + 1)
# G[0] = 1
# i = 1
# while i < (len(p)):
# j = i - 1
#
# while (ord(p[i]) - ord(p[j]) != 1) or (p[i] == "a" and p[j] != "z") or (p[i] != "a" and p[j] == "z") and i < len(p):
# G[i] = 1
# i += 1
# j += 1
#
# while i < len(p) and ((ord(p[i]) - ord(p[j]) == 1) or (p[i] == "a" and p[j] == "z") or (p[i] == "a" and p[j] == "z")):
#
# i += 1
# print(G)
# print(i)
# G[i] = self.sumSub(j, i)
#
# return sum(G[0:-2])
#
# def sumSub(self, j, i):
# sum = 0
# for k in range(i - j):
# sum += k
# print(sum)
def test():
p = "zababcdeabcaipfhi"
sol = Solution()
print(sol.findSubstringInWraproundString(p))
if __name__ == "__main__":
test()