String Basic

Catalogue

1. 1. Removol
   1. 1.1. Char Removal
   2. 1.2. 27. Remove Element
   3. 1.3. Char Removal II
2. 2. De-duplication
   1. 2.1. 26. Remove Duplicates from Sorted Array
   2. 2.2. 80. Remove Duplicates from Sorted Array II
   3. 2.3. Remove adjacent letters repeatedly
3. 3. Reversal
   1. 3.1. 344. Reverse String
   2. 3.2. 557. Reverse Words in a String III
   3. 3.3. 186. Reverse Words in a String II
   4. 3.4. 189. Rotate Array
4. 4. Char Replace
   1. 4.1. Word Replacement
   2. 4.2. 833. Find And Replace in String
   3. 4.3. 844. Backspace String Compare
5. 5. String to Number
   1. 5.1. 8. String to Integer (atoi)
   2. 5.2. 65. Valid Number
   3. 5.3. 504. Base 7
   4. 5.4. 12. Integer to Roman
6. 6. Encode and Decode
   1. 6.1. 394. Decode String
7. 7. Strobogrammatic Number
   1. 7.1. 246. Strobogrammatic Number
   2. 7.2. 247. Strobogrammatic Number II
   3. 7.3. 248. Strobogrammatic Number III
8. 8. String continuous count
   1. 8.1. 38. Count and Say

Popular representation of characters:

1. ASCII representation of a letter: A==65, a==97
2. Unicode : the latest version of Unicode contains a repertoire of more than 110,000 charaters covering 100 scripts and various symbols.

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???

• slow: all elements to the left hand side of slow pointer(excluding slow) are the final results to return
• fast: current index

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

• follow up : what if we want to reserve 2 duplicate elements?

80. Remove Duplicates from Sorted Array II

• you can just compare the current pointer with slow - 2 position

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

• follow up : what if we want to reserve k duplicate elements?

Remove adjacent letters repeatedly

• Stack or Two pointers

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)

186. Reverse Words in a String II

e.g. “I love Google” - “Google love I”

• sol1. split and reverse
  but not in-place in thie way!

• sol2. reverse twice(trick)

1. reverse each words “I love Google” - “I evol elgooG”
2. reverse the string “Google love I”

class Solution(object):
    def reverseWords(self, str):
        n = len(str)
        # Step 1. reverse each word
        start = 0
        for i in xrange(n+1):
            if i == n or str[i] == " ":
                end = i-1
                while start < end:
                    str[start], str[end] = str[end], str[start]
                    start += 1
                    end -= 1
                start = i + 1

        # Step 2. reverse all the sentences
        start, end = 0, n-1
        while start < end:
            str[start], str[end] = str[end], str[start]
            start += 1
            end -= 1

• Dicussion

1. 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.
2. 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”

189. Rotate Array

• use the same trick as we used in the reverse words in sentence!

  class Solution(object):
      def rotate(self, nums, k):
          n = len(nums)
          k = k % n
          self._reverse(nums, 0, n-k-1)
          self._reverse(nums, n-k, n-1)
          self._reverse(nums, 0, n-1)
  
      def _reverse(self, nums, start, end):
          while start < end:
              nums[start], nums[end] = nums[end], nums[start]
              start += 1
              end -= 1

Char Replace

Word Replacement

“student” -> “stuXXt”(den -> XX)

• Two Pointers

1. slow: all letters to the left hand side of slow are the results to return
2. fast: fast index to scan the whole string

• follow up
  s1 = “_“, s2 = “20%”

833. Find And Replace in String

• Replaced String part is longer than original part, How do you deal with that?

class Solution:
    def findReplaceString(self, S, indexes, sources, targets):
        n = len(indexes)
        res = []
        prev = 0
        for idx, src, target in sorted(zip(indexes, sources, targets)):
            if idx > prev:
                res.append(S[prev:idx])
                prev = idx

            if S[idx:idx+len(src)] != src:
                continue
            res.append(target)
            prev = idx + len(src)

        res.append(S[prev:])
        return ''.join(res)

844. Backspace String Compare

• Traverse Backwards!!!

  class Solution(object):
      def backspaceCompare(self, S, T):
          m, n = len(S), len(T)
          ps, pt = m-1, n-1
          while ps >= 0 or pt >= 0:
              # S
              backS = 0
              while ps >= 0 and (backS > 0  or S[ps] == '#'):
                  backS += 1 if S[ps] == '#' else -1
                  ps -= 1
  
              # T
              backT = 0
              while pt >= 0 and (backT > 0 or T[pt] == '#'):
                  backT += 1 if T[pt] == '#' else -1
                  pt -= 1
  
              if (pt < 0) ^ (ps < 0):
                  return False
  
              if pt >= 0 and ps >= 0 and S[ps] != T[pt]:
                  return False
  
              pt -= 1
              ps -= 1
          return True

String to Number

8. String to Integer (atoi)

• Take Care of Edge Cases!!!

class Solution:
    def myAtoi(self, str):
        n = len(str)        
        p = 0
        # filter the space
        while p < n and str[p] == ' ':
            p += 1

        # positive or negtive
        neg = False
        if p < n and str[p] in "+-":
            if str[p] == '-':
                neg = True
            p += 1

        num = 0
        while p < n and str[p].isnumeric():
            num = num * 10 + int(str[p])
            p += 1

        if neg:
            num = -num

        return min(2**31-1, max(-2**31, num))

65. Valid Number

• Define the state, Keep in mind : different states!!!

  class Solution:
      def isNumber(self, s):
          s = s.strip()
          states = [{'+-': 2, '0-9': 1, '.': 3},
                    {'0-9': 1, 'e': 5, '.': 4},
                    {'0-9': 1, '.': 3},
                    {'0-9': 4},
                    {'0-9': 4, 'e': 5},
                    {'0-9': 7, '+-': 6},
                    {'0-9': 7},
                    {'0-9': 7}]
          cur = 0
          for ch in s:
              if ch.isdigit():
                  flag = "0-9"
              elif ch in "+-":
                  flag = "+-"
              else:
                  flag = ch
  
              if flag not in states[cur]:
                  return False
              cur = states[cur][flag]
  
          return cur in [1, 4, 7]

504. Base 7

class Solution:
    def convertToBase7(self, num):
        if num == 0:
            return "0"

        sign = True if num < 0 else False
        num = abs(num)
        base7 = []
        while num > 0:
            base7.append(str(num%7))
            num = num // 7
        if sign:
            base7.append("-")
        res = ''.join(base7[::-1])
        return res

12. Integer to Roman

class Solution:
    def intToRoman(self, num):
        roman = {1000:'M', 500:'D', 100:'C', 50:'L', 10:'X', 5:'V', 1:'I'}
        res = []
        ns = [1000, 500, 100, 50, 10, 5, 1]
        for k in range(7):
            t = num // ns[k]
            if t == 0:
                continue

            num = num % ns[k]
            if t == 4:
                if len(res) == 0 or res[-1] != roman[ns[k-1]]:
                    res.append(roman[ns[k]] + roman[ns[k-1]])
                else:
                    res.pop()
                    res.append(roman[ns[k]] + roman[ns[k-2]])
            else:
                res.append(roman[ns[k]] * t)
        return ''.join(res)

Encode and Decode

394. Decode String

class Solution:
    def decodeString(self, s):
        stack = [[[], 1]] # repeat string array, times of repeat
        num = 0
        for ch in s:
            if ch.isdigit():
                num = num * 10 + (ord(ch) - ord('0'))
            elif ch == '[':
                stack.append([[], num])
                num = 0
            elif ch == ']':
                chs, k = stack.pop()
                stack[-1][0] += (chs * k)
            else:
                stack[-1][0].append(ch)
        return ''.join(stack[0][0])

Strobogrammatic Number

246. Strobogrammatic Number

class Solution(object):
    def isStrobogrammatic(self, num):
        dic = {0:0, 1:1, 6:9, 8:8, 9:6}
        left, right = 0, len(num)-1
        while left <= right:
            l, r = int(num[left]), int(num[right])
            if l not in dic or r not in dic:
                return False

            if dic[l] != r:
                return False

            left += 1
            right -= 1
        return True

247. Strobogrammatic Number II

class Solution(object):
    def findStrobogrammatic(self, n):
        self.n = n
        return self.helper(n)

    def helper(self, m):
        if m == 0:
            return [""]

        if m == 1:
            return ["0", "1", "8"]

        sub = self.helper(m - 2)
        res = []
        for s in sub:
            if m != self.n:
                res.append("0" + s + "0")

            for can in ["11", "88", "69", "96"]:
                res.append(can[0] + s + can[1])
        return res

248. Strobogrammatic Number III

class Solution(object):
    def strobogrammaticInRange(self, low, high):
        m, n = len(low), len(high)
        self.temp = {0:[""], 1:["1", "0", "8"]}
        self.memo = {1:["1", "0", "8"]}
        res = []
        for i in range(m, n+1):
            self.helper(i)

        cnt = 0
        blow, bhigh = int(low), int(high)
        for i in range(n, m-1, -1):
            temp = self.memo[i]
            for item in temp:
                if blow <= int(item) <= bhigh:
                    cnt += 1
        return cnt


    def helper(self, k):
        if k in self.temp:
            return self.temp[k]

        sub = self.helper(k-2)
        res = []
        for s in sub:
            for can in ("11", "88", "69", "96"):
                res.append(can[0] + s + can[1])

        self.memo[k] = res

        ans = []
        for s in sub:
            ans.append("0" + s + "0")

        self.temp[k] = res + ans
        return res + ans

String continuous count

38. Count and Say

class Solution(object):
    def countAndSay(self, n):
        if n == 1:
            return "1"

        prev = self.countAndSay(n-1)
        ans = []
        for ch in prev:
            if not ans or ch != ans[-1][0]:
                ans.append([ch, 1])
            else:
                ans[-1][1] += 1

        res = []
        for ch, cnt in ans:
            res.append(str(cnt) + ch)

        return ''.join(res)