Removol

Char Removal

Remove a/some particular chars from a String. Example: string input = "student", remove "u and n" -> output:"stdet"

Attention : String and Array erase API!!!

class Solution:
    def charRemoval(self, s, ch):
        chs = list(s)
        start = 0
        for i in xrange(len(chs)):
            if chs[i] not in ch:
                chs[start] = chs[i]
            start += 1
        retrun ''.join(chs[:start])

27. Remove Element

class Solution(object):
    def removeElement(self, nums, val):
        start = 0
        for i in xrange(len(nums)):
            if nums[i] != val:
                nums[start] = nums[i]
                start += 1
        return start

Char Removal II

Remove all leading/trailing and duplicate empty spaces(only leave one empty space if duplicated spaces happen) from the input string.

De-duplication

26. Remove Duplicates from Sorted Array

What's the phisical definition of the two pointers???

class Solution(object):
    def removeDuplicates(self, nums):
        if not nums:
            return 0

        start = 1
        for i in xrange(1, len(nums)):
            if nums[i] != nums[start-1]:
                nums[start] = nums[i]
                start += 1
        return start

80. Remove Duplicates from Sorted Array II

counter 也可以最好的方式是直接和slow-2比较！

class Solution(object):
    def removeDuplicates(self, nums):
        if len(nums) <= 2:
            return len(nums)

        slow = 2
        for i in xrange(2, len(nums)):
            if nums[i] != nums[slow-2]:
                nums[slow] = nums[i]
                slow += 1
        return slow

Remove adjacent letters repeatedly

Stack or Two pointers

Substring Matching

28. Implement strStr()

Time : O(m * n)

class Solution(object):
    def strStr(self, haystack, needle):
        m, n = len(needle), len(haystack)
        for i in xrange(n-m+1):
            if haystack[i:i+m] == needle:
                return i
        return -1

Reversal

344. Reverse String

two pointers : left, right or start, end

class Solution(object):
  def reverseString(self, s):
      chs = list(s)
      s, e = 0, len(s)-1
      while s < e:
          chs[s], chs[e] = chs[e], chs[s]
          s += 1
          e -= 1
      return ''.join(chs)

557. Reverse Words in a String III

class Solution(object):
    def reverseWords(self, s):
        words = s.split()
        for i in xrange(len(words)):
            words[i] = words[i][::-1]
        return ' '.join(words)

"I love Google" - "Google love I"

sol1. split and reverse
sol2. reverse twice(trick)
reverse each words "I love Google" - "I evol elgooG"
reverse the string "Google love I"
Dicussion
The idea for "I LOVE GOOGLE" can be combined to form more complex prblem. e.g., if we have empty/leading/trailing spaces in the input.
The idea can be extended to other probem as well!
- "abcdef" sift to the left by two steps "cdefab"
- step1. seperate reverse "bafedc"
- step2. reverse the word "cdefab"

String Basic