- 软件开发
- 【Leetcode】467. Unique Substrings in Wraparound String
class Solution(object):
def findSubstringInWraproundString(self
, p
):
"""
dp[i]表示以p[i]结尾的最长的串
这道题的关键是处理重复的串，对于结尾相同的串，我们取最长，用一个字典即可实现
"""
dict = {}
dp
= [1] * len(p
)
for i
in range(len(dp
)):
if i
== 0:
pass
else:
if self
.difference
(p
[i
], p
[i
-1]) == 1:
dp
[i
] += dp
[i
-1]
if p
[i
] in dict:
dict[p
[i
]] = max(dict[p
[i
]], dp
[i
])
else:
dict[p
[i
]] = dp
[i
]
return sum(dict.values
())
def difference(self
, a
, b
):
if a
== "a" and b
== "z":
return 1
else:
return (ord(a
) - ord(b
))
class Solution1(object):
"""
faster
"""
def findSubstringInWraproundString(self
, p
):
dp
= [1] * len(p
)
dict = {}
for i
in range(len(dp
)):
if i
== 0:
pass
else:
if ord(p
[i
]) - ord(p
[i
-1]) == 1 or (p
[i
] == "a" and p
[i
-1] == "z"):
dp
[i
] += dp
[i
-1]
dict[p
[i
]] = max(dict.get
(p
[i
], 0), dp
[i
])
return sum(dict[key
] for key
in dict)
