[LeetCode] Easy - 942. DI String Match

Source From Here
Question

How-To

view plaincopy to clipboardprint?

1. #!/usr/bin/env python3  
2. class Solution:  
3.     def diStringMatch(self, S):  
4.         r'''  
5.                     IDID  
6.         IDID    -> 02143  
7.                     III  
8.         III     -> 0123  
9.                     DDI  
10.         DDI     -> 3214  
11.   
12.         Solution:  
13.         Find ranges of D and reverse the numbers within that range.  
14.         For example:  
15.         1) Find range of D  
16.         IDID => [(1, 2), (3, 4)]  
17.   
18.         2) Reverse the D range  
19.                        --       --  
20.             (1, 2) => 01234 -> 02134  
21.                          --       --  
22.             (3, 4) => 02134 -> 02143  
23.         '''  
24.         s_len = len(S)  
25.         plist = list(range(s_len + 1))  
26.   
27.   
28.         # 1) Collecting reverse tuple  
29.         rt_list = []  
30.         i = 0  
31.         while i < len(S):  
32.             if S[i] == 'D':  
33.                 dpair = [i]  
34.                 for j in range(i+1, s_len):  
35.                     if S[j] == 'D':  
36.                         i += 1  
37.                     else:  
38.                         break  
39.   
40.                 i += 1  
41.                 dpair.append(i)  
42.   
43.                 rt_list.append(dpair)  
44.             else:  
45.                 i += 1  
46.   
47.         # 2) Work on reverse tuple  
48.         for rt in rt_list:  
49.             plist[rt[0]:rt[1]+1] = plist[rt[0]:rt[1]+1][::-1]  
50.   
51.         print('S={}; rt_list={}; plist={}'.format(S, rt_list, plist))  
52.         return plist  

Supplement
* FAQ - How do I reverse a part (slice) of a list in Python?

>>> alist = list(range(10))
>>> alist
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> alist[1:5] = alist[1:5][::-1] # Reverse 1, 2, 3, 4 -> 4, 3, 2, 1
>>> alist
[0, 4, 3, 2, 1, 5, 6, 7, 8, 9]