0791. Custom Sort String - kumaeki/LeetCode GitHub Wiki

0791. Custom Sort String


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.

Note:

  • order has length at most 26, and no character is repeated in order.
  • str has length at most 200.
  • order and str consist of lowercase letters only.

解法1

先统计每个字符有多少个, 然后按照order的顺序来排列, 在order中没有出现的, 就接在后面.

class Solution {
    public String customSortString(String order, String str) {
        int[] memo = new int[26];
        for(char c : str.toCharArray())
            memo[c - 'a']++;
        
        StringBuilder res = new StringBuilder();
        for(char c : order.toCharArray()){
            appendStr(c, memo[c - 'a'], res);
            memo[c - 'a'] = 0;
        }
        
        for(int i = 0; i < 26; i++)
            appendStr((char)(i + 'a'), memo[i], res);
        
        return res.toString();
    }
    
    private String appendStr(char c, int count, StringBuilder sb){
        for(int i = 0; i < count; i++)
            sb.append(c);
        return sb.toString();
    }
}