[leetcode] Custom Sort String

791. Custom Sort String

原题&翻译

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S 和 T 是两个由小写字幕组成的字符串。S 没有重复字符。

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.

S 存储序列随机。我们需要置换 T 中元素序列使其和 S 序列一致。说的详细一点就是,如果在 S 中存储的 x 在 y 前方,则,返回的的 x 必须在 y 前。

Return any permutation of T (as a string) that satisfies this property.

任意返回字符串 T 排序必须满足这个属性。

比如,输入:

S = "cba"
T = "abcd"

输出: "cbad"

分析:

"a", "b", "c" 在 S 中出现,所以 "a", "b" 三个字母的序列应该呈现为:"c", "b", "a"。
由于 “d” 没有出现在 S 中,所以它可以出现在任何位置。

注意:

  • S 长度限制为 26,且没有重复的元素。

  • T 长度限制在 200 以内。

  • S 和 T 都有且只有小写字母组成。


解题思路

解法一

不需要多余的空间,不需要特殊的数据结构,4 ms。
设置一个变量 complete 记录已经完成排序的字符,在第二层循环内,和 S 对比,如果匹配成功就置换到 complete 标记的位置上,并且 complete++,排序完成后,无顺序的字符会扔到 T 字符串的末尾。

class Solution {
public:
    string customSortString(string S, string T) {
        int complete = 0;
        for(int i=0;i<S.size();i++){
            for(int j=complete;j<T.size();j++){
                if(T[j] == S[i]) {
                    T[j] = T[complete];
                    T[complete] = S[i];
                    ++complete;
                }
            }
        }
        return T;
    }
};

解法二

lailianqi 的做法,看不懂,原样搬运。

class Solution {
  public:
    string customSortString(string S, string T) {
        sort(T.begin(), T.end(),
             [&](char a, char b) { return S.find(a) < S.find(b); });
        return T;
    }
};