791 Custom Sort String 自定義字符串排序
Description:
You are given two strings order and s. All the words 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.
Example:
Example 1:
Input: order = "cba", s = "abcd"
Output: "cbad"
Explanation:
"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.
Example 2:
Input: order = "cbafg", s = "abcd"
Output: "cbad"
Constraints:
1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters.
All the characters of order are unique.
題目描述:
字符串S和 T 只包含小寫字符。在S中，所有字符只會(huì)出現(xiàn)一次窜骄。
S 已經(jīng)根據(jù)某種規(guī)則進(jìn)行了排序。我們要根據(jù)S中的字符順序?qū)進(jìn)行排序虑瀑。更具體地說(shuō)，如果S中x在y之前出現(xiàn)畏腕，那么返回的字符串中x也應(yīng)出現(xiàn)在y之前缴川。
返回任意一種符合條件的字符串T。
示例 :
輸入:
S = "cba"
T = "abcd"
輸出: "cbad"
解釋:
S中出現(xiàn)了字符 "a", "b", "c", 所以 "a", "b", "c" 的順序應(yīng)該是 "c", "b", "a".
由于 "d" 沒(méi)有在S中出現(xiàn), 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的輸出描馅。
注意:
S的最大長(zhǎng)度為26，其中沒(méi)有重復(fù)的字符而线。
T的最大長(zhǎng)度為200铭污。
S和T只包含小寫字符。
思路:
- 哈希表
用哈希表或者一個(gè)數(shù)組記錄 s 的字符個(gè)數(shù)
先將 order 中出現(xiàn)的字符按序插入到結(jié)果
剩下的字符直接接在結(jié)果的最后 - 雙指針
用兩個(gè)指針?lè)謩e指向 order 和 s
每次找到 order 的字符, 將 order 的字符交換到 s 的前面
時(shí)間復(fù)雜度為 O(n), 空間復(fù)雜度為 O(1)
代碼:
C++:
class Solution
{
public:
string customSortString(string order, string s)
{
int index = 0;
for (const auto& c : order) for (int i = index; i < s.size(); i++) if (s[i] == c) swap(s[i], s[index++]);
return s;
}
};
Java:
class Solution {
public String customSortString(String order, String s) {
int[] count = new int[26];
for (char c: s.toCharArray()) ++count[c - 'a'];
StringBuilder result = new StringBuilder();
for (char c: order.toCharArray()) while(count[c - 'a']-- > 0) result.append(c);
for (char c = 'a'; c <= 'z'; ++c) while(count[c - 'a']-- > 0) result.append(c);
return result.toString();
}
}
Python:
class Solution:
def customSortString(self, order: str, s: str) -> str:
return ''.join(sorted(list(s), key=lambda x: order.find(x)))
