共计 1733 个字符，预计需要花费 5 分钟才能阅读完成。
题目
S and T are strings composed of lowercase letters. In S, no letter occurs more than once.
S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.
Return any permutation of T (as a string) that satisfies this property.
Example :
Input:
S = “cba”
T = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in S, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in S, it can be at any position in T. “dcba”, “cdba”, “cbda” are also valid outputs.
Note:
S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.
题目地址
讲解
这道题刚开始一直思路挺混乱的，只知道一定得用 HashMap 来减少搜索字符的时间（遍历需要很多遍）。正确的思路是这样的：首先我们需要遍历一遍 T，把其中的字符分为两类，一类是在 S 中有的，一类是在 S 中没有的。而且将它们出现的次数以 HashMap 这种数据结构记录下来。而这个分类的过程中，是需要搜索 S 的，所以我们要提前把 S 弄成一张哈希表，这样就不用遍历 S 很多遍了。最后我们遍历一遍 S，按照顺序，将 S 中的元素又在 mapT 中的放到 result 中，同时放一个就 remove 一个缩小 mapT 的大小。然后再将剩下的 mapT 中的元素放到 result 中。
Java 代码
class Solution {
public String customSortString(String S, String T) {
Map<Character, Integer> mapT = new HashMap<>();
Set<Character> mapS = new HashSet<>();
for(int i=0;i<S.length();i++){
mapS.add(S.charAt(i));
}
for(int i=0;i<T.length();i++){
Integer count= mapT.get(T.charAt(i));
if(mapS.contains(T.charAt(i))){
if(count==null){
mapT.put(T.charAt(i),1);
}else{
mapT.put(T.charAt(i),count+1);
}
}else{
if(count==null){
mapT.put(T.charAt(i),-1);
}else{
mapT.put(T.charAt(i),count-1);
}
}
}
char[] result = new char[T.length()];
int indexBegin=0;
int indexEnd = T.length()-1;
for(int i=0;i<S.length();i++){
Integer count = mapT.get(S.charAt(i));
if(count!=null){
while(count>0){
result[indexBegin++] = S.charAt(i);
count–;
}
mapT.remove(S.charAt(i));
}
}
for(Character c:mapT.keySet()){
Integer count = mapT.get(c);
while(count<0){
result[indexEnd–] = c;
count++;
}
}
return String.valueOf(result);
}
}
