forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathChaedie.py
More file actions
49 lines (40 loc) · 1.25 KB
/
Chaedie.py
File metadata and controls
49 lines (40 loc) · 1.25 KB
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
"""
Solution:
1) encode: 각 글자의 앞에 글자수와 # 라는 delimiter 를 붙여 stringify 한다.
2) decode: length 를 참고삼아 word를 따내어 result 배열을 만든다.
encode:
Time: O(n) (n: strs 배열의 길이만큼 연산)
Space: O(1)
decode:
Time: O(n) (n: s 의 길이만큼 연산)
Space: O(m) (m: decode 이후 배열의 길이)
"""
class Codec:
def encode(self, strs: List[str]) -> str:
"""Encodes a list of strings to a single string."""
result = ""
for word in strs:
result += str(len(word))
result += "#"
result += word
return result
def decode(self, s: str) -> List[str]:
"""Decodes a single string to a list of strings."""
i = 0
result = []
length = ""
while i < len(s):
# find number
length = ""
while s[i] is not "#":
length += s[i]
i += 1
# find #
i += 1
# find word
result.append(s[i : i + int(length)])
i += int(length)
return result
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))