如果第i个字符之前在字符串中没有出现过,那么f(i)=f(i-1) + 1,显然f(0)=1.
如果第i个字符之前在字符串中出现过,那么情况就复杂点,我们先计算第i个字符和它上次出现在字符串中的位置的距离,并记为d,接着就有两种情况。第一种。d<=f(i-1),此时,第i个字符出现在了f(i-1)对应的最长字符串中,因此f(i)=d。这种情况是能够保证字符是连续的。当我们在f(i-1)对应的最长字符串找到了第i个字符的位置索引,就删除f(i-1)对应的字符串下,i字符索引之前的所有字符。第二种情况,d>f(i-1),此时第i个字符出现在了f(i-1)对应的最长字符串之前,那么依然有f(i)=f(i-1)+1
书上分析如下:
我在leetcode上找到一题最长子序列的:
代码测试:
code:
class Solution:
def lengthOfLongestSubstring(self, s):
position = [] # 标记不重复的字符列表
char_distance = 0 # 第i 个字符与该字符上一次出现的距离
maxLength = 0 # 存储最长子序列
for index, x in enumerate(s):
if x not in position:
position.append(x)
else:
char_distance = len(position) - position.index(x) # 计算距离
if char_distance <= len(position):
position = position[position.index(x) + 1 :]
position.append(x)
else:
position.append(x)
if len(position) > maxLength:
maxLength = len(position) # 找到最长的子序列, abcabcbb测试案例
return maxLength
if __name__ == "__main__":
s = 'arabcacfr'
ss = Solution()
print(ss.lengthOfLongestSubstring(s))