forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
palindrome-rearrangement-queries.py
88 lines (81 loc) · 4.26 KB
/
palindrome-rearrangement-queries.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
# Time: O(26 + d * n + d * q)
# Space: O(26 + d * n)
# prefix sum, freq table
class Solution(object):
def canMakePalindromeQueries(self, s, queries):
"""
:type s: str
:type queries: List[List[int]]
:rtype: List[bool]
"""
def check(left1, right1, left2, right2):
def same(left, right):
return all(prefixs1[right+1][i]-prefixs1[left][i] == prefixs2[right+1][i]-prefixs2[left][i] for i in xrange(d))
min_left, max_left = min(left1, left2), max(left1, left2)
min_right, max_right = min(right1, right2), max(right1, right2)
if not (prefix[min_left]-prefix[0] == prefix[-1]-prefix[max_right+1] == 0):
return False
if min_right < max_left: # non-overlapped
return prefix[max_left]-prefix[min_right+1] == 0 and same(min_left, min_right) and same(max_left, max_right)
# overlapped
if (left1 == min_left) == (right1 == max_right): # inside another
return same(min_left, max_right)
# not inside another
p1, p2 = (prefixs1, prefixs2) if min_left == left1 else (prefixs2, prefixs1)
diff1 = [(p1[min_right+1][i]-p1[min_left][i])-(p2[max_left][i]-p2[min_left][i]) for i in xrange(d)]
diff2 = [(p2[max_right+1][i]-p2[max_left][i])-(p1[max_right+1][i]-p1[min_right+1][i]) for i in xrange(d)]
return diff1 == diff2 and all(x >= 0 for x in diff1) # test case: s = "aabbba", queries = [[0,1,3,4]]
lookup = [-1]*26
d = 0
for x in s:
if lookup[ord(x)-ord('a')] != -1:
continue
lookup[ord(x)-ord('a')] = d
d += 1
prefix = [0]*(len(s)//2+1)
prefixs1 = [[0]*d for _ in xrange(len(s)//2+1)]
prefixs2 = [[0]*d for _ in xrange(len(s)//2+1)]
for i in xrange(len(s)//2):
x, y = lookup[ord(s[i])-ord('a')], lookup[ord(s[~i])-ord('a')]
prefix[i+1] = prefix[i]+int(x != y)
for j in xrange(d):
prefixs1[i+1][j] = prefixs1[i][j]+int(j == x)
prefixs2[i+1][j] = prefixs2[i][j]+int(j == y)
return [check(q[0], q[1], (len(s)-1)-q[3], (len(s)-1)-q[2]) for q in queries]
# Time: O(26 * n + 26 * q)
# Space: O(26 * n)
# prefix sum, freq table
class Solution2(object):
def canMakePalindromeQueries(self, s, queries):
"""
:type s: str
:type queries: List[List[int]]
:rtype: List[bool]
"""
def check(left1, right1, left2, right2):
def same(left, right):
return all(prefixs1[right+1][i]-prefixs1[left][i] == prefixs2[right+1][i]-prefixs2[left][i] for i in xrange(26))
min_left, max_left = min(left1, left2), max(left1, left2)
min_right, max_right = min(right1, right2), max(right1, right2)
if not (prefix[min_left]-prefix[0] == prefix[-1]-prefix[max_right+1] == 0):
return False
if min_right < max_left: # non-overlapped
return prefix[max_left]-prefix[min_right+1] == 0 and same(min_left, min_right) and same(max_left, max_right)
# overlapped
if (left1 == min_left) == (right1 == max_right): # inside another
return same(min_left, max_right)
# not inside another
p1, p2 = (prefixs1, prefixs2) if min_left == left1 else (prefixs2, prefixs1)
diff1 = [(p1[min_right+1][i]-p1[min_left][i])-(p2[max_left][i]-p2[min_left][i]) for i in xrange(26)]
diff2 = [(p2[max_right+1][i]-p2[max_left][i])-(p1[max_right+1][i]-p1[min_right+1][i]) for i in xrange(26)]
return diff1 == diff2 and all(x >= 0 for x in diff1) # test case: s = "aabbba", queries = [[0,1,3,4]]
prefix = [0]*(len(s)//2+1)
prefixs1 = [[0]*26 for _ in xrange(len(s)//2+1)]
prefixs2 = [[0]*26 for _ in xrange(len(s)//2+1)]
for i in xrange(len(s)//2):
x, y = ord(s[i])-ord('a'), ord(s[~i])-ord('a')
prefix[i+1] = prefix[i]+int(x != y)
for j in xrange(26):
prefixs1[i+1][j] = prefixs1[i][j]+int(j == x)
prefixs2[i+1][j] = prefixs2[i][j]+int(j == y)
return [check(q[0], q[1], (len(s)-1)-q[3], (len(s)-1)-q[2]) for q in queries]