FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
LeetCode-Solutions/Python/rotate-string.py at master · pythonpeixun/LeetCode-Solutions · GitHub
pythonpeixun
/
LeetCode-Solutions
Public
forked from
kamyu104/LeetCode-Solutions
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
LeetCode-Solutions
/
Python
/
rotate-string.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
99 lines (83 loc) · 2.53 KB
Breadcrumbs
LeetCode-Solutions
/
Python
/
rotate-string.py
Copy path
File metadata and controls
99 lines (83 loc) · 2.53 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
89
90
91
92
93
94
95
96
97
98
# Time: O(n)
# Space: O(1)
class
Solution
(
object
):
def
rotateString
(
self
,
A
,
B
):
"""
:type A: str
:type B: str
:rtype: bool
"""
def
check
(
index
):
return
all
(
A
[(
i
+
index
)
%
len
(
A
)]
==
c
for
i
,
c
in
enumerate
(
B
))
if
len
(
A
)
!=
len
(
B
):
return
False
M
,
p
=
10
**
9
+
7
,
113
p_inv
=
pow
(
p
,
M
-
2
,
M
)
b_hash
,
power
=
0
,
1
for
c
in
B
:
b_hash
+=
power
*
ord
(
c
)
b_hash
%=
M
power
=
(
power
*
p
)
%
M
a_hash
,
power
=
0
,
1
for
i
in
xrange
(
len
(
B
)):
a_hash
+=
power
*
ord
(
A
[
i
%
len
(
A
)])
a_hash
%=
M
power
=
(
power
*
p
)
%
M
if
a_hash
==
b_hash
and
check
(
0
):
return
True
power
=
(
power
*
p_inv
)
%
M
for
i
in
xrange
(
len
(
B
),
2
*
len
(
A
)):
a_hash
=
(
a_hash
-
ord
(
A
[(
i
-
len
(
B
))
%
len
(
A
)]))
*
p_inv
a_hash
+=
power
*
ord
(
A
[
i
%
len
(
A
)])
a_hash
%=
M
if
a_hash
==
b_hash
and
check
(
i
-
len
(
B
)
+
1
):
return
True
return
False
# Time: O(n)
# Space: O(n)
# KMP algorithm
class
Solution2
(
object
):
def
rotateString
(
self
,
A
,
B
):
"""
:type A: str
:type B: str
:rtype: bool
"""
def
strStr
(
haystack
,
needle
):
def
KMP
(
text
,
pattern
):
prefix
=
getPrefix
(
pattern
)
j
=
-
1
for
i
in
xrange
(
len
(
text
)):
while
j
>
-
1
and
pattern
[
j
+
1
]
!=
text
[
i
]:
j
=
prefix
[
j
]
if
pattern
[
j
+
1
]
==
text
[
i
]:
j
+=
1
if
j
==
len
(
pattern
)
-
1
:
return
i
-
j
return
-
1
def
getPrefix
(
pattern
):
prefix
=
[
-
1
]
*
len
(
pattern
)
j
=
-
1
for
i
in
xrange
(
1
,
len
(
pattern
)):
while
j
>
-
1
and
pattern
[
j
+
1
]
!=
pattern
[
i
]:
j
=
prefix
[
j
]
if
pattern
[
j
+
1
]
==
pattern
[
i
]:
j
+=
1
prefix
[
i
]
=
j
return
prefix
if
not
needle
:
return
0
return
KMP
(
haystack
,
needle
)
if
len
(
A
)
!=
len
(
B
):
return
False
return
strStr
(
A
*
2
,
B
)
!=
-
1
# Time: O(n^2)
# Space: O(n)
class
Solution3
(
object
):
def
rotateString
(
self
,
A
,
B
):
"""
:type A: str
:type B: str
:rtype: bool
"""
return
len
(
A
)
==
len
(
B
)
and
B
in
A
*
2
Back
|
FazBrowse Home
|
New Git URL