Solution to LeetCode 5 Longest Palindromic Substring, LeetCode 6 Zigzag Conversion, LeetCode 14 Longest Common Prefix, and LeetCode 31 Next Permutation.
LeetCode 5
Longest Palindromic Substring (Medium) [link]
Dynamic Programming. Define dp[i][j] as whether or not the string[i:j] is a palindromic substring. The recurrent relation is dp[i][j] = dp[i+1][j-1] & (s[i]==s[j]). The base cases: when len(s)==1 return True, when len(s)==2 if s[0]==s[1] return True else False. The final result is the longest j-i+1 among all dp[i][j]==True.
Time complexity O(n^2). Space complexity O(n^2).
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(set(s)) == 1:
return s
n = len(s)
start, end, maxL = 0,0,0
dp = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(i):
dp[j][i] = (s[i]==s[j]) and ((i-j < 2) | dp[j+1][i-1])
if dp[j][i] and maxL < i-j+1:
maxL = i-j+1
start = j
end = i
dp[i][i] = True
return s[start:end+1]
LeetCode 6
Zigzag Conversion (Medium) [link]
Simulate the row index change. Time complexity O(n). Space complexity O(n).
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows < 2:
return s
res = ["" for _ in range(numRows)]
flag = -1
i=0
for c in s:
res[i] += c
if i == 0 or i == numRows-1:
flag = -flag
i += flag
return "".join(res)
LeetCode 14
Longest Common Prefix (Easy) [link]
1] Horizontal scan. Time complexity O(mn).
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
cnt = len(strs)
prefix = strs[0]
for i in range(1, cnt):
prefix = self.check(prefix, strs[i])
if not prefix:
return ""
return prefix
def check(self, s1, s2):
length = min(len(s1), len(s2))
ind = 0
while ind < length and s1[ind] == s2[ind]:
ind += 1
return s1[:ind]
2] Vertical scan. Time complexity O(mn).
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
minL = len(strs[0])
for i in range(len(strs)):
if len(strs[i]) <= minL:
minL = len(strs[i])
cur = strs[0]
for i in range(minL):
if any(cur[i] != strs[j][i] for j in range(1,len(strs))):
return cur[:i]
return cur[:minL]
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
cur = strs[0]
for i in range(len(cur)):
if any(i == len(strs[j]) or cur[i] != strs[j][i] for j in range(1,len(strs))):
return cur[:i]
return cur
LeetCode 31
Next Permutation (Medium) [link]
Idea: 1] To make the list a little bit larger, find a smaller value on the left and a larger value on the right, make sure they are as close as possible, exchange their position; 2] reorder the values on the right of the larger value in ascending order, e.g. [4,5,2,6,3,1] -> [4,5,3,6,2,1] -> [4,5,3,1,2,6]
The algorithm is: 1] start from the right, find the value s[i] whose right subsequences[i+1:] is in descending order and buts[i:] is not in descending order. 2] start from the right again, find the first value s[j] that’s larger than s[i], exchange their positions. 3] order the subsequence on the right of the s[j] value in ascending order.
Note that if we cannot find s[i], which means the whole array is in descending order and it’s the largest array. We only need step 3 to reverse the array and get the smallest array.
Time complexity O(n). Space complexity O(1).
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = len(nums)-2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
j = len(nums)-1
if i >=0:
while j >= i and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left = i+1
right = len(nums)-1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -=1
