Find Permutation

1387 단어
https://www.lintcode.com/problem/find-permutation/description
public class Solution {
    /**
     * @param s: a string
     * @return: return a list of integers
     */
    public int[] findPermutation(String s) {
        // write your code here
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i + 1;
        }
        int decreaseCount = 0;
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length()) {
                if (decreaseCount > 0) {
                    int end = i;
                    int start = end - decreaseCount;
                    swap(dp, start, end);
                }
                break;
            }
            char c = s.charAt(i);
            if (c == 'D') {
                decreaseCount++;
            } else {
                if (decreaseCount != 0) {
                    int end = i;
                    int start = end - decreaseCount;
                    swap(dp, start, end);
                    decreaseCount = 0;
                }
            }
        }

        return dp;
    }

    private void swap(int[] dp, int start, int end) {
        while (start < end) {
            int temp = dp[start];
            dp[start] = dp[end];
            dp[end] = temp;
            start++;
            end--;
        }
    }
}

좋은 웹페이지 즐겨찾기