程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Sword finger offer python:44 Longest substring without duplicate characters

編輯:Python

subject : Please find the longest substring in the string that does not contain duplicate characters , Calculate the length of the longest substring .

for example :

“abcabcbb” “abc” The length is 3

“bbbbb” “b” The length is 1

“dvdf” “vdf” The length is 3

Analytic process , See also leetcode: Power button

Dynamic programming + Hashtable (python Dictionary ), It can also be understood as two pointers .

Code :

 

class Solution:
def func(self , s):
if len(s) == 0:
return 0
elif len(s) == 1:
return 1
save = dict() # Save the maximum position of each letter , Immediate replacement with duplicate
res = 0
j = 0
for i in range(len(s)):
if i == 0:
res = 1
else:
if s[i] not in save.keys():
res += 1
else:
j = save[s[i]]
res = max(res , (i - 1) - j) # Dynamic equation
save[s[i]] = i
print('i = {} , j = {} , save = {}'.format(i , j , save))
return res
s = Solution()
a = 'abcabcbb'
print(s.func(a))

Output :

 


  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved