791. Custom Sort String 自定义字符串排序

@TOC

# 题目描述

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"
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:

1. S has length at most 26, and no character is repeated in S.
2. T has length at most 200.
3. S and T consist of lowercase letters only.

# 题目大意

S是一个自定义的字母表顺序，现在要把T中的字符按照S的顺序进行排序。如果T中有S中不存在的字符，那么可以处在结果的任何位置。

# 解题方法

# 按顺序构造字符串

``````from collections import Counter
count = Counter("Hello World!")
print count['8']
##输出0
``````

``````from collections import Counter
class Solution(object):
def customSortString(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
count = Counter(T)
for s in S:
count[s] = 0
for c in count:
``````

C++代码如下：

d.count(c)只会返回0或者1，想要得到次数使用d[c]，但是这个在不存在的情况下会新增key=c。最好使用find()返回的是迭代器。

``````class Solution {
public:
string customSortString(string S, string T) {
map<char, int> d;
for (char c : T) d[c]++;
string res;
for (char c : S) {
for (int i = 0; i < d[c]; i++) {
res += c;
}
d[c] = 0;
}
for (auto k : d) {
if (k.second) {
for (int i = 0; i < k.second; i++) {
res += k.first;
}
}
}
return res;
}
};
``````

``````(6) fill constructor
string (size_t n, char c);
Fills the string with n consecutive copies of character c.
``````

``````class Solution {
public:
string customSortString(string S, string T) {
map<char, int> d;
for (char c : T) d[c]++;
string res = "";
for (char c : S) {
res += string(d[c], c);
d[c] = 0;
}
for (auto k : d) {
res += string(k.second, k.first);
}
return res;
}
};
``````

# 排序

python代码如下：

``````class Solution(object):
def customSortString(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
pos = collections.defaultdict(int)
for i in range(len(S)):
pos[S[i]] = i
res = sorted(T, key = lambda x : pos[x])
return "".join(res)
``````

# 日期

2018 年 2 月 26 日 2018 年 12 月 4 日 —— 周二啦！ 2019 年 1 月 6 日 —— 打球打的腰酸背痛