题目大意：给你字符的顺序，让你排序一个字符串。
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.
|
1 2 3 4 5 6 7 8 |
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:
Shas length at most26, and no character is repeated inS.Thas length at most200.SandTconsist of lowercase letters only.
Solution 1: HashTable + Sorting
- Store the order of char in a hashtable
- Sort the string based on the order
Time complexity: O(nlogn)
Space complexity: O(128)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua // Running time: 2 ms class Solution { public: string customSortString(string S, string T) { vector<int> order(128, INT_MAX); int i = 0; for (char c: S) if (order[c] == INT_MAX) order[c] = ++i; std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){ return order[c1] < order[c2]; }); return T; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment