forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcompare-version-numbers.py
More file actions
36 lines (29 loc) · 1.2 KB
/
compare-version-numbers.py
File metadata and controls
36 lines (29 loc) · 1.2 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
"""
i1 and i2 is the pointer we point to the starting point.
Character before i1 and i2 we already processed.
When they are set to -1, the whole string are already processed.
#for-loop can't find the '.' any more. [0]
after two version is fully processed and couldn't find which is larger, return 0. [1]
Time Complexity is O(N).
N is the length of those version, because we potentially loop through them once.
Space Complexity is O(1).
Because we only store two pointers and two integer.
"""
class Solution(object):
def compareVersion(self, version1, version2):
def getVersion(version, start):
if start==-1: return 0, -1
for i in xrange(start, len(version)):
if version[i]=='.':
return int(version[start:i]), i+1
return int(version[start:]), -1 #[0]
i1 = i2 = 0
while True:
sub_version1, i1 = getVersion(version1, i1)
sub_version2, i2 = getVersion(version2, i2)
if sub_version1>sub_version2:
return 1
elif sub_version1<sub_version2:
return -1
elif i1==-1 and i2==-1: #[1]
return 0