给定两个字符串 order
和 s
。order
的所有单词都是 唯一 的,并且以前按照一些自定义的顺序排序。
对 s
的字符进行置换,使其与排序的 order
相匹配。更具体地说,如果在 order
中的字符 x
出现字符 y
之前,那么在排列后的字符串中, x
也应该出现在 y
之前。
返回 满足这个性质的 s
的任意排列 。
示例 1:
输入: order = "cba", s = "abcd" 输出: "cbad" 解释: “a”、“b”、“c”是按顺序出现的,所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。 因为“d”不是按顺序出现的,所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
示例 2:
输入: order = "cbafg", s = "abcd" 输出: "cbad"
提示:
1 <= order.length <= 26
1 <= s.length <= 200
order
和s
由小写英文字母组成order
中的所有字符都 不同
方法一:哈希表 + 自定义排序
将字符串中的字符按照
时间复杂度
方法二:字符计数
统计
然后把在
时间复杂度
class Solution:
def customSortString(self, order: str, s: str) -> str:
cs = list(s)
m = {v: i for i, v in enumerate(order)}
cs.sort(key=lambda x: m.get(x, -1))
return ''.join(cs)
class Solution:
def customSortString(self, order: str, s: str) -> str:
cnt = Counter(s)
ans = []
for c in order:
ans.append(cnt[c] * c)
cnt[c] = 0
for c in s:
ans.append(cnt[c] * c)
cnt[c] = 0
return ''.join(ans)
class Solution {
public String customSortString(String order, String s) {
Map<Character, Integer> m = new HashMap<>();
for (int i = 0; i < order.length(); ++i) {
m.put(order.charAt(i), i);
}
List<Character> cs = new ArrayList<>();
for (char c : s.toCharArray()) {
cs.add(c);
}
cs.sort((a, b) -> m.getOrDefault(a, -1) - m.getOrDefault(b, -1));
StringBuilder ans = new StringBuilder();
for (char c : cs) {
ans.append(c);
}
return ans.toString();
}
}
class Solution {
public String customSortString(String order, String s) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) {
++cnt[c - 'a'];
}
StringBuilder ans = new StringBuilder();
for (char c : order.toCharArray()) {
while (cnt[c - 'a']-- > 0) {
ans.append(c);
}
}
for (char c : s.toCharArray()) {
while (cnt[c - 'a']-- > 0) {
ans.append(c);
}
}
return ans.toString();
}
}
class Solution {
public:
string customSortString(string order, string s) {
vector<int> cnt(26);
for (char c : s) ++cnt[c - 'a'];
string ans = "";
for (char c : order) {
while (cnt[c - 'a']-- > 0) {
ans += c;
}
}
for (char c : s) {
while (cnt[c - 'a']-- > 0) {
ans += c;
}
}
return ans;
}
};
func customSortString(order string, s string) string {
cnt := make([]int, 26)
for _, c := range s {
cnt[c-'a']++
}
ans := []rune{}
for _, c := range order {
for cnt[c-'a'] > 0 {
ans = append(ans, c)
cnt[c-'a']--
}
}
for _, c := range s {
for cnt[c-'a'] > 0 {
ans = append(ans, c)
cnt[c-'a']--
}
}
return string(ans)
}