[数据结构与算法]LeetCode.791 Custom Sort String(自定义字符串排序)

1.题目

You are given two strings order and s. All the words of?order?are?unique?and were sorted in some custom order previously.

Permute the characters of?s?so that they match the order that?order?was sorted. More specifically, if a character?x?occurs before a character?y?in?order, then?x?should occur before?y?in the permuted string.

Return?any permutation of?s?that satisfies this property.

2.样例

- 样例1
Input: order = "cba", s = "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.
- 样例2
Input: order = "cbafg", s = "abcd"
Output: "cbad"

- 限制条件

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order?and?s?consist of lowercase English letters.
• All the characters of?order?are?unique.

?3.题解

- 题目：的意思：给定字符串order（其中每个字符都是唯一的，即只有26个小写字母），按照oder中的每个字母出现的顺序，我们需要对s字符串也需按照在order中的字母排序进行排序（返回一种排序即可）。

- 代码：

class Solution {
    public String customSortString(String order, String s) {
        // 思路：对order字符串的顺序作为模版，将s的字符串分别统计对应的次数，匹配到order没有相关字符时说明已经匹配完了，直接将剩下的字符按照顺序拼接即可
        if(order==null||order.length()==0||s==null||s.length()==0){
            return null;
        }
        
        int []times=new int[256];
        char [] chs=s.toCharArray();
        for(char ch:chs){
            times[ch]++;
        }
        
        char [] templateChs=order.toCharArray();
        char [] res=new char[chs.length];
        int index=0;
        for(char ch:templateChs){
            if(times[ch]==0){
                continue;
            }
            
            while(times[ch]>0){
                res[index++]=ch;
                times[ch]--;
            }
        }
        
        for(int i=0;i<times.length;i++){
            while(times[i]>0){
                res[index++] = (char) i;
                times[i]--;
            }
        }
        return String.valueOf(res);
    }
}