活跃农民
- 积分
- 401
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-10-12
- 最后登录
- 1970-1-1
|
Sep Palindrome
214
# HARD
# Input: "abcd"
# reverse input => as rev = "dcba"
# compare s[:n-i] with rev[i:]
# abcd vs dcba
# abc vs cba
# ab vs ba
# a vs a => i == 3
# the same substring is the overlapped part of the result, thus rev[:i] + s is the result
# Time O(N^2) Space O(n)
# KMP prefix table
# this reduced the substring time to O(1)
# Time O(N) Space O(N)
132
# HARD
# 1. build a palindrome table
# palindrome[i][j] => True if s[i:j] is palindromic else False
# 2. dp => [MaxInt] * (n+1) represent every chunk of s
# dp[0] = 0 since no chunk can be splited
# dp[i] = min(dp[i], dp[j]+1) for j in range(i) if palindromic[j][i-1]
# Time O(N^2) Space O(N^2)
267
# MEDIUM
# since this is looking for permutation, the Time would be O(N!)
# 1. first check if the input can form a palindrome => only <=1 odd occured char can used
# 2. only permutate the half of the input == permutation II
# eg. input = "aabb"
# only permutate ["a","b"], append reversed(input) to the end
# Time O(N/2 !) Space O(N)
336
# HARD
# input ["abcd","dcba","lls","s","sssll"]
# scan each word of the input and store {word:index} into a dict:
# 1. check if the reversed(word) also in dict and the index is not same
# 2. check suffix of a word
# eg. word = "lls"
# "l" is palindromic => check reversed("ls") in dict
# "ll" is palindromic => check reversed("s") in dict => True
# 3. check prefix of a word
# Time O(K^2 * N) Space O(N)
|
|