Python O(n) solution with stack


  • 3
    H

    To find the smallest lexicographical permutation, we start with a list of increasing order. All "I"s are already satisfied. With any sequence of continuous 'D''s, we reverse the list. Since the range of the numbers within the sequence is unchanged, the "I"'s are not influenced.

    class Solution(object):
        def findPermutation(self, s):
            """
            :type s: str
            :rtype: List[int]
            """
            
            l = len(s)
            stack,res = [],[]
            for i in range (l):
                cur_num = i+1
                if s[i] == 'D':
                    stack.append(cur_num)
                if s[i] == 'I':
                    stack.append(cur_num)
                    while stack:
                        res.append(stack.pop())
            # last digit
            res.append(l+1)
            while stack:
                res.append(stack.pop())
                
            return res
    

  • 0
    R

    Nice clean implementation! Java Version based on the same logic.

    public class Solution {
        public int[] findPermutation(String s) {
            ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
            int[] sol = new int[s.length() + 1];
            int index = 0;
            
            int len = s.length();
            
            
            for (int i = 0; i < len; i++) {
                int curr = i + 1;
                if (s.charAt(i) == 'D') {
                    stack.addFirst(curr);
                }
                
                if (s.charAt(i) == 'I') {
                    stack.addFirst(curr);
                    while(!stack.isEmpty()) {
                        sol[index++] = stack.removeFirst();
                    }
                }
            }
            
            
            sol[index++] = len + 1;
            while (!stack.isEmpty())
                sol[index++] = stack.removeFirst();
    
            return sol;
            
        }
    }
    
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.