From today on in the following year, I’ll try to solve one LeetCode problem every other day. I’ll write this blog as a record to the algorithms and my own experience.

07-29 #5 Longest Palindromic Substring

Can be solved with dynamic programming with: \[ dp[i][j] = \begin{cases} 1 \text{ if i =j} \\ dp[i + 1][j - 1]\text{ if } S_i = S_j \end{cases} \] Note the loop order should first be the shortest sub string, then longer ones. However the time complexity and space complexity are both \(O(n^2)\), so directly expand from each character will have the same time complexity while having the space complexity of \(O(1)\), which is a more efficient algorithm.

07-25 #4 Median of Two Sorted Arrays

Given two sorted array, find the median value for them, with time complexity of \(O(log(m+n))\). Binary search is needed in this case. Finding the answer can be seen as deleting some \(k\) elements of these two array, where \(k = (m + n) / 2\).

Set offset for two array as 0 in the first, compare n1[offset1] and n2[offset2], if n1 smaller than n2 we can move offset n1 forward, vice versa. When \(offset1 + offset2 == k\), jump out of the loop. The step of moving forward is (todel - deleted) / 2, a classical binary search.

Note when offset reach out the boundary, let’s say n1, the answer is the m th element, where m = n2.size() - n1.size().

07-23 #3 Longest Substring Without Repeating Characters

Using size and len as sliding window to control the start and end of the strings. Once the repeated characters found, move the start flag rightwards. An efficient approach is using an array tag to mark the time of occurrence for each character. (m[128] = {0}).

07-20 #2 Add Two Numbers

Big number sumation with reversed linked-list. Can be solved with a loop and a carry bit. Note the loop is not supposed to end when there’s still a carry flag left, thus checking flag is necessary at the entry point.