Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

```
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
rows, cols = len(text1) + 1, len(text2) + 1
grid = [[0] * cols
```

]]>Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

```
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
rows, cols = len(text1) + 1, len(text2) + 1
grid = [[0] * cols for _ in range(rows)]
for n in range(1, cols):
for m in range(1, rows):
if text2[n - 1] == text1[m - 1]:
grid[m][n] = 1 + grid[m - 1][n - 1]
else:
grid[m][n] = max(grid[m - 1][n], grid[m][n - 1])
print(grid)
return grid[rows - 1][cols - 1]
```

]]>For China user:

]]>Singapore is one of the best place I've ever been! I love there so much that bring me a lot in memory.

For China user:

]]>Anyway, Let's start STRING GAMES!

Let's start with some basic (not that basic) operations on String by Python:

0. Stack!!!

You should be aware that **Most of the String problems** is associate with stack!

That's right!

]]>String matters, especially in interview questions and Leetcode!

Anyway, Let's start STRING GAMES!

Let's start with some basic (not that basic) operations on String by Python:

0. Stack!!!

You should be aware that **Most of the String problems** is associate with stack!

That's right! sometimes we tend to use operations quite similar to compiler, thus we need to be familiar with everything in **STACK**

Stack operations

```
stack = []
# push into stack
stack.append(1) # [1]
stack.append(2) # [1, 2]
stack.append(3) # [1, 2, 3]
# pop out the top element
top = stack.pop() # top = 3, stack -> [1, 2]
# get the top element
top = stack[-1] # top = 2, stack -> [1, 2] (similar to peek)
```

But in fact, how we use python queue in leetcode problem is that:

a) We use head-tail linked list (deque):

```
from collections import deque
de1 = deque()
de1.append(1) # [1]
de1.append(2) # [1, 2]
de1.appendleft(5) # [5, 1, 2]
de1.appendleft(6) # [6, 5, 1, 2]
print(de1.count(1)) # 1 appears 1
de1.reverse() # [2, 1, 5, 6]
de1.extend([444, 555, 666]) # [2, 1, 5, 6, 444, 555, 666]
de1.pop() # [2, 1, 5, 6, 444, 555]
de1.popleft() # [1, 5, 6, 444, 555]
```

b) Priority queue:

```
import queue
q = queue.Queue()
q.put(3)
q.put(5)
q.put(4)
full = q.full() # True
while not q.empty():
print(q.get()) # [3, 5, 4]
# min first
pq = queue.PriorityQueue()
pq.put(3)
pq.put(5)
pq.put(4)
while not pq.empty():
print(pq.get()) # [3, 4, 5]
# max first
pq = []
pq.append(3)
pq.append(5)
pq.append(4)
pq.sort(reverse=1)
while pq:
print(pq.pop())
```

By the way, we should know how to implement a queue through **2 stack**, which will be push = O(1) and pop = O(1)

This is the problem of Leetcode 232:

```
class MyQueue:
def __init__(self):
self.LI = [] # Last In
self.FO = [] # First Out
def push(self, x):
self.LI.append(x)
def pop(self):
if not self.FO:
while self.LI:
self.FO.append(self.LI.pop())
return self.FO.pop()
def peek(self):
if not self.FO:
return self.LI[0]
else:
return self.FO[-1]
def empty(self):
return not self.LI and not self.FO
```

Or if we want one stack to represent queue, it is also OK!

```
class MyQueue(object):
def __init__(self):
self.st = []
def push(self, x):
if len(self.st) == 0:
self.st.append(x)
return
tmp = self.st.pop(-1)
self.push(x)
self.st.append(tmp)
def pop(self):
return self.st.pop(-1)
def peek(self):
return self.st[-1]
def empty(self):
return len(self.st) == 0
```

- Reverse String:

```
ori_str = "abcd"
reverse_str = ori_str[::-1] #come to "dcba"
```

- Find SubString:

```
super_str = "abcde"
sub_str = "bc"
not_sub_str = "abd"
pos = super_str.find(sub_str) #pos = 1, find from beginning
pos_2 = super_str.rfind(sub_str) # pos_2 = 1, find from the rear
pos_3 = super_str.find(not_sub_str) # pos_2 = -1, not substring found
```

- index & count

```
ori_str = "abcde"
pos = ori_str.index("c") # pos = 2
pos_1 = ori_str.rindex("b") # pos_1 = 1
```

- count

```
ori_str = "abcdeaa"
num = ori_str.count("a") # num = 3
num_1 = ori_str.count("a", 0, 3) # num_1 = 1
```

- Split, Partition, Split with line

```
str = "123123123"
str_list = str.split('2') # ['1', '31', '31', '3']
str_tuple = str.partition('2') # ('1', '2', '3123123')
str='abc\nabc\nabc\nabc'
str_list = str.splitlines() # ['abc', 'abc', 'abc', 'abc']
```

- Judgement

```
str0='0123abcd'
str1='12345'
str2='abcdef'
str3=' '
str0.startswith('0') # check if start with 0, True
str0.endswith('0') # check if end with 0, False
str1.isalnum() # check if the str all consist of alphabet and number, True
str2.isalpha() # check if the str all consist of alphabet, True
str0.isdigit() # check if the str all consist of digit, False
str3.isspace() # check if all consist of space, True
```

- ATTENTION: String cannot be changed, but we can change by..

```
str0 = "what"
# str0[2] = "i" # This is not allowed!!!
list_str0 = list(str0)
list_str0[2] = "i"
str0 = "".join(list_str0)
print(str0)
```

- Mapping

```
date = "2019-8-15"
Y, M, D = map(int, date.split('-'))
# Y = 2019, M = 8, D = 15
```

Description: return true if `s`

is an anagram of `t`

```
Input: s = "anagram", t = "nagaram"
Output: true
```

Solution 1 with Collections (inner Hash Map):

```
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
# Counter(s) = Counter({'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1})
return Counter(s) == Counter(t)
```

Solution 2 with HashMap (By ourself) in O(n):

```
def isAnagram(self, s: str, t: str) -> bool:
map1 = {}
if s == '' and t == '':
return True
if len(s) != len(t):
return False
for itr in range(len(s)):
map1[s[itr]] = map1.setdefault(s[itr], 0) + 1
map1[s[itr]] = map1.setdefault(t[itr], 0) + 1
for i in map1.values():
if i != 0:
return False
return True
```

Solution 1 with Hash Map:

```
def longestPalindrome(self, s: str) -> int:
map1 = {}
for item in range(len(s)):
map1[s[item]] = map1.setdefault(s[item], 0) + 1
res = 0
for item in map1.values():
res += (item // 2) * 2
if res < len(s):
res += 1
return res
```

Description:

Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Solution 1 with find function:

```
def isIsomorphic(self, s, t):
# e.g. s = "eggggwe"
# [s.find(i) for i in s] = [0, 1, 1, 1, 1, 5, 0]
return [s.find(i) for i in s] == [t.find(j) for j in t]
```

Solution 2 with dict function:

```
def isIsomorphic(self, s, t):
if len(s) != len(t): return False
map1 = {}
for i in range(len(s)):
if s[i] in map1:
if map1[s[i]] != t[i]:
return False
elif t[i] in map1.values():
return False
else:
map1[s[i]] = t[i]
return True
```

```
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
```

Solution 1 with find function:

```
res = 0
def countSubstrings(self, s: str) -> int:
for i in range(len(s)):
self.extension(s, i, i);
self.extension(s, i, i+1);
return self.res
def extension(self, s: str, start: int, end: int):
while start >= 0 and end <= len(s) - 1 and s[start] == s[end]:
start -= 1
end += 1
self.res += 1
```

```
Input: x = 121
Output: true
Input: x = -121
Output: false
Could you solve it without converting the integer to a string?
```

Solution 1 simple implement:

```
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x > 0 and x % 10 == 0): return False
ori = x
res = 0
while x != 0:
digit = x % 10
x = x // 10
res = digit + res * 10
return ori == res
```

Solution 2 with half loop:

```
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x > 0 and x % 10 == 0): return False
right = 0
while x > right:
right = right * 10 + x % 10
x = x // 10
return x == right or x == right // 10
```

```
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
```

Solution 1 with group by character:

```
def countBinarySubstrings(self, s: str) -> int:
groups = [1]
for i in range(1, len(s)):
if s[i] != s[i - 1]:
groups.append(1)
else:
groups[-1] += 1
ans = 0
for i in range(1, len(groups)):
ans += min(groups[i-1], groups[i])
return ans
```

Solution 1 with linear scanning, not using a list, but use two var to store pre and cur:

```
def countBinarySubstrings(self, s: str) -> int:
preLen, curLen, count = 0, 1, 0
for i in range(1, len(s)):
if s[i] == s[i - 1]:
curLen += 1
else:
preLen = curLen
curLen = 1
if preLen >= curLen:
count += 1
return count
```

]]>Fortunately, I got the experience to go to have a course in HKBU..

Here is what happened 👇

For China user:

]]>Bit operation plays a cardinal role in the fundamental calculation in machine-level language. I'm currently enrolled at Carnegie Mellon University as a master student in the Software Engineering program. One of the renowned courses must be "Introduction to Computer System".

After the first lab, namely Datalab. I spent enormous time on bit-level calculation and practice. To recall what I learned, how it was used in the practice of leetcode, here give the two parts: tricks & corresponding leetcode problems.

Bit operations contain the following:

&, |, ^, ~, <<, >>, !

In the above operation, I love shift and XOR operations. Why?

Let's see what can they do!

Mask is quite crucial in bit computation. This is set to 0 since all the bit operation always depend on MASKS!

Here are a list of masks that is quite useful:

(I use int type here)

```
# a) obtain FFFFFFFF
mask_FFFFFFFF = ~0
# b) obtain 0000FFFF
mask_0000FFFF = 1 << 16 - 1
# c) obtain FFFF0000
mask_0000FFFF = ~0 << 16
# d) obtain 55555555
mask_55555555 = "Not Available now"
```

```
# gives u * 2^3
u << 3
# gives u * 24
(u << 5) - (u << 3)
```

Remember that this is also good when u is a negative number. (But not the case on the boundary of type)

such as:

```
# good case
u = -1 # u = 0xFFFFFFFF --- u = -1
u <<= 1 # u = 0xFFFFFFFE --- u = -2
u <<= 1 # u = 0xFFFFFFFC --- u = -4
```

Consider the bad case as always!

```
#bad case
u = 2147483648 # u = 0x7FFFFFFF
u << 1 # u = 0xFFFFFFFF
v = -2147483648 # v = 0x10000000
v << 1 # v = 0x00000000
```

In the right shift, it is not always rational divided due to rounding, it is quite similar to `5/2 = 2`

in C.

Notice that we should consider positive and negative cases separately.

For positive cases:

For negative cases:

It is wrong, because in negative cases, we should round up rather round down! So we need to change the right shift code to:

```
# this denote for if x is a negative number of divide 2 with rounding
x = -5
x = x + (1 << k) - 1) >> k
# In this way, it is similar to x >> k in positive number
```

Eliminate the last 1 in binary

n & (n - 1)

```
01011101 &
01011100
--------
01011100
```

Obtain the last 1 in binary

n & (-n)

```
10110100 &
01001100
--------
00000100
```

```
x ^ 0 = x
x ^ x = 0
x ^ -1 = ~x
```

Description: get the numbers of bit differences in binary

```
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
```

Solution 1 with O(n):

```
def hammingDistance(self, x: int, y: int) -> int:
temp = x ^ y #get the diff numbers
count = 0
while temp != 0:
temp &= temp - 1 #eliminate 1 at a time
count += 1
return count
```

Solution 2 with special function in O(n):

```
def hammingDistance(self, x: int, y: int) -> int:
bin(x ^ y).count('1')
```

Solution 3 (Fastest!) with shift in O(n):

```
def hammingDistance(self, x, y):
res = x ^ y
counter = 0
for i in range(32):
if res >> i & 1 == 1: #using shift is much faster!!!!!
counter += 1
return counter
```

Description: find the number in the list that is single

```
Input: [4,1,2,1,2]
Output: 4
```

Solution 1 with O(n):

Consider that:

```
x ^ x = 0
x ^ 0 = x
```

Then use loooooop for entire list, the operation would be:

```
4 ^ 1 ^ 2 ^ 1 ^ 2 => 4
```

Thus, the solution would be:

```
def singleNumber(self, nums: List[int]) -> int:
res = 0
for item in nums:
res ^= item
return res
```

Input: [3,0,1]

Output: 2

Solution 1 use XOR in O(1):

```
def missingNumber(self, nums: List[int]) -> int:
ret = 0
for i in range(len(nums)):
ret ^= i ^ nums[i]
return ret ^ len(nums) # I love this one!
```

Why?

Consider that:

`ret = (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1)`

and return `len(nums)`

if `ret = 0`

return `ret`

if `ret != 0`

Solution 2 use enumerate in O(1):

```
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
for index, item in enumerate(nums):
if index != item:
return index
else: # else is a good usage for "for"
return nums[-1] + 1
```

Solution 1: that is **not** using bit operation, but I like it pretty much, since it use the set() to eliminate duplicates, btw, this solution is also suitable for the above problem 136:

```
def singleNumber(self, nums: List[int]) -> List[int]:
res = set()
for item in nums:
if item in res: res.remove(item)
else: res.add(item)
return res
```

Solution 2: bit operation solution:

```
# The bitmask will have all the differences between x and y (the two singles).
# x has 0 and y has 1 or vice-versa in those bits.
# You take one difference, the rightmost one.
# Iterate through array again dividing into two.
# The ones which has 1 on the rightmost different bit into one group and those who have 0 into another group.
# Group1 : [x^a^a^b^b] = x
# Group2 : [y^c^c^d^d] = y
# bitmask^x = y;
def singleNumber(self, nums: List[int]) -> List[int]:
bitmask = 0
for num in nums:
bitmask ^= num
diff = bitmask & (-bitmask)
x = 0
for num in nums:
if num & diff:
x ^= num
return [x, bitmask ^ x]
```

Solution 1: again, here I would like to reverse the bits by using the smart reverse method in python:

```
def reverseBits(self, n: int) -> int:
return int('{:032b}'.format(n)[::-1], 2)
```

`{:032b}'.format(n)`

is for revert int value to string with 32 bit binary

`[::-1]`

is the smart way to reverse a string in Python

`int(x, 2)`

is to output the int value as a binary number

Solution 2:

```
def reverseBits(self, n: int) -> int:
ret, power = 0, 31
while n:
ret += (n & 1) << power
n >>= 1
power -= 1
return ret
```

Solution: use eliminate last 1 method:

KEY POINT: Remember to consider 0!!!

```
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0
```

Solution:

```
def isPowerOfFour(self, n: int) -> bool:
if(n<0):
return False
b = bin(n)
if(b.count("1") == 1 and (b[3:].count("0") % 2 == 0)):
return True
return False
```

Solution 1:

```
def hasAlternatingBits(self, n: int) -> bool:
return n & (n >> 1) == 0 and n & (n >> 2) == n >> 2
```

Solution 2:

```
def hasAlternatingBits(self, n: int) -> bool:
# 10101010101
# + 1010101010 ( number >> 1 )
# ---------------
# = 11111111111
# & 100000000000
# ---------------
# = 0 ( power of two )
n = n ^ (n >> 1)
return n & n + 1 == 0
```

]]>2018, the year I came to Hong Kong for one month. This city is incredibly large and crowded. The reason why I stayed here for such a long time is that I was learning the course: Television Studio Production at Hong Kong Baptist University. In my free time, I took this video...(kinda Vlog)

For China users, please direct to:

]]>This is the pre-assignment of 18-652 Foundation of Software Engineering in CMU. Tech used:

Front-end:

- HTML/CSS, Bootstrap 5, JQuery(JavaScript), EJS

Back-end:

- Node.js, Express.js, Socket.io, express-session, bcrypt.js

Try this now!!!

Introduction video of this project:

]]>