Case 1: a[j] should be kept: a[i]=a[j], i++, j++
Case 2: a[j] should not be kept: j++
classSolution(object):defremove(self,input,t):""" input: string input, string t return: string"""# write your solution here slow, fast =0,0 toremove =set(t) array =list(input)for fast inrange(len(array)):if array[fast]notin toremove: array[slow]=array[fast] slow+=1return''.join(array[:slow])
Step 1: from left to right: we only deal with the cases where the letter repeats >=2 times; the case that appeared only once are simply copied. In the meantime, we need to count how many times a letter only repeats once. eg. count=1
Step 2: enlarge the string by 'count', and from right to left: do similar steps.
Sliding window
longest substring that each char occurs at most k times
[L(slow), R(fast)]: each char occurs at most k times within this window
HashMap: <char, count>
def remove(str):
lst = list(str)
i,j = 0,0
while j<len(lst):
if lst[j] not in ['u', 'n']
lst[i] = lst[j]
i+=1
j+=1
return ''.join(lst[:i])
print(remove("student"))
def remove(str):
lst = []
j = 0
while j<len(str):
if str[j] not in ['u', 'n']
lst.append(str[j])
j+=1
return ''.join(lst)
print(remove("student"))
class Solution(object):
def removeSpaces(self, input):
"""
input: string input
return: string
"""
# write your solution here
if not input:
return input
array = list(input)
slow = 0
for fast in range (len(array)):
if array[fast]==' ' and (fast==0 or array[fast-1]==' '):
continue
array[slow]=array[fast]
slow+=1
if (slow>0 and array[slow-1]==' '):
slow-=1
return ''.join(array[:slow])
def remove_spaces(str):
if not str:
return str
lst = list(str)
i,j = 0,0
while j < len(lst):
## Case 2 and Case 3
if lst[j]!=' ' or (i!=0 and lst[i-1]!=' '):
lst[i]=lst[j]
i+=1
j+=1
if i>0 and lst[i-1] ==' ':
i-=1
return ''.join(lst[:i])
def remove_spaces(str):
if not str:
return str
lst = []
for fast in xrange(len(lst)):
if str[fast]==' ' and (fast==0 or lst[fast-1]==' '):
continue
lst.append(str[fast])
if len(lst)>0 and lst[-1] ==' ':
lst.pop()
return ''.join(lst)
def remove_duplicate(str):
if not str or len(str)<2:
return str
lst = list(str)
slow, fast = 1, 1
while fast<len(lst):
if lst[fast]!=lst[slow-1]:
lst[slow]=lst[fast]
slow+=1
fast+=1
return ''.join(lst[:slow])
def remove_duplicate(str):
if not str or len(str)<2:
return str
fast = 0
lst = []
while fast<len(lst):
if lst[fast]==0 or lst[-1]!=str[fast]:
lst.append(str[fast])
fast+=1
return ''.join(lst[:slow])
class Solution(object):
def deDup(self, input):
"""
input: string input
return: string
"""
# write your solution here
if not input:
return input
array = list(input)
slow = 0
for fast in range (len(array)):
if fast==0 or array[fast]!=array[slow-1]:
array[slow]=array[fast]
slow+=1
return ''.join(array[:slow])
class Solution(object):
def deDup(self, input):
"""
input: string input
return: string
"""
# write your solution here
if not input or len(input)<1:
return input
lst = []
fast = 0
while fast < len(input):
if len(lst)>0 and input[fast]==lst[-1]: #易错点 lst[-1]但是忘了>0的前提
while fast<len(input) and lst[-1]==input[fast]: #易错点 fast++的过程中可能比input本身还大
fast+=1
fast+=1
lst.pop()
else:
lst.append(input[fast])
fast+=1
return ''.join(lst)
def reverse_helper(lst, left, right):
while left<right:
lst[left], lst[right] = lst[right], lst[left]
left += 1
right -= 1
def reverse_helper(lst, left, right):
while left<right:
lst[left], lst[right] = lst[right], lst[left]
left += 1
right -= 1
def reverse_string(string):
lst = list(string)
reverse_helper(lst, 0, len(lst)-1)
i = 0
left = i
right = i
while i < len(lst):
if i==len(lst)-1 or lst[i+1]==' ';
right = i
reverse_helper(lst, left, right)
left = i + 2
i += 1
return ''.join(lst)
class Solution:
def strstr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype int
"""
if not needle:
return 0
for h in xrange(len(haystack)-len(needle)+1): #[l,r)
for n in xrange(len(needle)):
if haystack[h+n]!=needle[n]:
break
else: # when the for look terminates naturally (without early break)
return h
return -1
Class RabinKarp:
def __init__(self):
self.base = 26
self.mod = 997
def strstr(self, haystack, needle):
if len(needdle)>len(haystack):
return -1
hay_hash, nhash = 0,0
power = 1
for i in range(len(needle)):
power = power*self.base%self.mod if i!=0 else 1
hay_hash = (hay_hash * self.base + ord(haystack[i])%self.mod
nhash = (nhash*self.base+ord(needle[i]))%self.mod
for i in range(len(needle), len(haystack)):
if hay_hash ==nhash and needle == haystack[i-len(needle):i]:
return i-len(needle)
hay_hash -= (power*ord(haystack[i-len(needle)]))%self.mod
if hay_hash <0:
hay_hash+=self.mod
hay_hash=(hay_hash*self.base+ord(haystack[i]))%self.mod
if hay_hash==nhash and needle ==haystack[len(haystack)-len(needle)]:
return len(haystack) - len(needle)
return -1
rk=RabinKarp()
print(rk.strstr('bacbabababacaab', 'abaca'))
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not needle:
return 0
if len(haystack)<len(needle):
return -1
Q, W = 10**9+0, 256
HW = 1
for i in xrange(1, len(needle)):
HW = (HW*W)%Q
needle_hash, haystack_hash = 0,0
for i in xrange(len(needle)):
needle_hash = (W*needle_hash+ord(needle[i]))%Q
haystack_hash = (W*haystack_hash+ord(haystack[i]))%Q
if needle_hash == haystack_hash:
return 0
for i in xrange(len(needle), len(haystack)):
haystack_hash = (haystack_hash -HW*ord(haystack[i-len(needle)])%Q+Q)%Q
haystack_hash = (haystack_hash*W+ord(haystack[i]))%Q
if needle_hash==haystack_hash
return i -len(needle)+1
return -1
