自定义字符串排序【LC791】

You are given two strings order and s. All the characters 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.

给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回 满足这个性质的 s 的任意排列 。

参加了双周赛+周赛，都只A了2.5题，最后一题就都只卡了一点点，好气，下周继续努力

• 思路：先使用哈希表统计字符串s中出现的字母和个数，然后将字母按order的顺序进行构造，order中不存在的字母按照字典顺序进行存放

• 实现

class Solution {
    public String customSortString(String order, String s) {
        int[] flag = new int[26];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++){
            flag[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < order.length(); i++){
            char c = order.charAt(i);
            while (flag[c - 'a'] > 0){
                sb.append(c);
                flag[c-'a']--;
            }
        }
        for (int i = 0; i < flag.length; i++){
            while (flag[i] > 0){
                sb.append((char)('a' + i));
                flag[i]--;
            }
        }
        return new String(sb);
    }
}

。复杂度

• 时间复杂度：O ( n + m )
• 空间复杂度：O ( 26 )