05 August 2008
自定义字符串排序
字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。
S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。
返回任意一种符合条件的字符串T。
示例:
输入: S = “cba”
T = “abcd”
输出: “cbad”
解释:
S中出现了字符 “a”, “b”, “c”, 所以 “a”, “b”, “c” 的顺序应该是 “c”, “b”, “a”. 由于 “d” 没有在S中出现, 它可以放在T的任意位置. “dcba”, “cdba”, “cbda” 都是合法的输出。
注意:
S的最大长度为26，其中没有重复的字符。
T的最大长度为200。
S和T只包含小写字符。
首先找出在 T 中出现的所有的 S 的元素，并且将这些元素按照 S 中出现的相对顺序排序，然后把 T 中出现的但不在 S 中的元素添加到排好序的字符串中，就得到了我们想要的结果。
在将 T 中出现的但不在 S 中的元素添加到字符串时，无序关注顺序，因为这些元素并没有在 S 中出现，不需要满足排序关系。
算法
一种巧妙的实现方法是统计 T 中每个字符出现的次数，把结果存储在数组 count 中，count[char] 表示字符 char 出现的次数。然后把在 S 中出现的字符按照在 S 中的相对顺序排列，剩余字符添加到当前字符串的后面，最终排好序的字符串顺序为 S + (未在 S 中出现的字符)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public String customSortString(String S, String T) {
// count[char] = the number of occurrences of 'char' in T.
// This is offset so that count[0] = occurrences of 'a', etc.
// 'count' represents the current state of characters
// (with multiplicity) we need to write to our answer.
int[] count = new int[26];
for (char ch : T.toCharArray())
count[ch - 'a']++;
// result will be our final answer. We use StringBuilder to join
// the answer so that we more efficiently calculate a
// concatenation of strings.
StringBuilder result = new StringBuilder();
// Write all characters that occur in S, in the order of S.
for (char ch : S.toCharArray()) {
for (int i = 0; i < count[ch - 'a']; ++i)
result.append(ch);
// Setting count[char] to zero to denote that we do
// not need to write 'char' into our answer anymore.
count[ch - 'a'] = 0;
}
// Write all remaining characters that don't occur in S.
// That information is specified by 'count'.
for (char c = 'a'; c <= 'z'; ++c) {
// result.append(String.valueOf(c).repeat(Math.max(0, count[c - 'a'])));
for (int i = 0; i < count[c - 'a']; ++i) {
result.append(c);
}
}
return result.toString();
}
}
常规解法， 用PQ和HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public String customSortString(String S, String T) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < S.length(); ++i) { // 记住order字符串中某字符最后出现的位置，这样确定先后
map.put(S.charAt(i), i);
}
PriorityQueue<Character> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
StringBuilder leftOutChars = new StringBuilder("");
for (int i = 0; i < T.length(); ++i) {
if (map.containsKey(T.charAt(i))) {
pq.offer(T.charAt(i));
} else {
leftOutChars.append(T.charAt(i));
}
}
StringBuilder newString = new StringBuilder("");
while (!pq.isEmpty()) {
newString.append(pq.poll());
}
String result = newString + leftOutChars.toString();
return result;
}
}