791. Custom Sort String

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

order and str are strings composed of lowercase letters. In order, no letter occurs more than once.

order was sorted in some custom order previously. We want to permute the characters of str so that they match the order that order was sorted. More specifically, if x occurs before y in order, then x should occur before y in the returned string.

Return any permutation of str (as a string) that satisfies this property.

Example:

Input:
order = "cba"
str = "abcd"
Output: "cbad"
Explanation:
"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Code

class Solution {
    public String customSortString(String order, String str) {
        int[] count = new int[26];
        // 统计每个字符
        for (char c : str.toCharArray()) {
            count[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        // 按照order的顺序加入每个str中的字符
        for (char c : order.toCharArray()) {
            for (int i = 0; i < count[c - 'a']; ++i) {
                sb.append(c);
            }
            count[c - 'a'] = 0;
        }
        // 加入剩下的字符
        for (char c = 'a'; c <= 'z'; ++c) {
            for (int i = 0; i < count[c - 'a']; ++i) {
                sb.append(c);
            }
        }

        return sb.toString();
    }
}

class Solution {
    class LetterOrder {
        String letter;
        int order;

        LetterOrder(String letter, int order) {
            this.letter = letter;
            this.order = order;
        }
    }

    public String customSortString(String order, String str) {
        int[] dict = new int[26];
        Arrays.fill(dict, Integer.MAX_VALUE);
        for (int i = 0; i < order.length(); i++) {
            char c = order.charAt(i);
            dict[c - 'a'] = i;
        }

        PriorityQueue<LetterOrder> queue = new PriorityQueue<>((a, b) -> {
            return a.order - b.order;
        });

        for (char c : str.toCharArray()) {
            LetterOrder letterOrder = new LetterOrder(String.valueOf(c), dict[c - 'a']);
            queue.offer(letterOrder);
        }

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            sb.append(queue.poll().letter);
        }

        return sb.toString();
    }
}