CustomSortString [source code]
public class CustomSortString {
static
/******************************************************************************/
class Solution {
public String customSortString(String S, String T) {
int[] counts = new int[26];
for (char c : T.toCharArray ())
counts[c - 'a']++;
char[] res = new char[T.length ()];
int pos = 0;
for (int i = 0; i < S.length (); i++) {
char c = S.charAt (i);
if (counts[c - 'a'] > 0) {
while (--counts[c - 'a'] >= 0)
res[pos++] = c;
}
}
for (int i = 0; i < 26; i++) {
if (counts[i] > 0) {
while (--counts[i] >= 0)
res[pos++] = (char) (i + 'a');
}
}
return new String (res);
}
}
/******************************************************************************/
public static void main(String[] args) {
CustomSortString.Solution tester = new CustomSortString.Solution();
}
}
如果S的所有的letter在T当中都出现, 这题就太trivial了, 这题的难点应该是比如S当中的一部分, 其实不出现在T当中的时候, 怎么办;
另一个难点是, 说了S里面没有重复, 但是T里面可能有啊; 怎么处理;
这道题最后行云流水, 飞速敲完, 然后一次AC, 自己都服了我自己了;
速度是4ms (NA).
注意--counts[c - 'a'] >= 0这个写的, 这种东西也别想太复杂, 就在脑子里面举个例子, 如果count是3, 你想要走几个循环: 希望header判断的是(before iteration)是2,1,0, 就可以了, 所以先--, 然后要取等号; 这两个都是对应的;
editorial
Approach #1: Count and Write [Accepted]
Intuition
Let's first write to our answer the elements of T that occur in S, in order of S. After, we'll write any elements of T we didn't write. This obviously keeps all the ordering relationships we wanted.
In the second write, the order doesn't matter because those elements aren't in S, so there are no ordering relationships these elements have to satisfy.
Algorithm
The trick is to count the elements of T. After we have some count[char] = (the number of occurrences of char in T), we can write these elements in the order we want. The order is S + (characters not in S in any order).
For more details on the algorithm, please see the inlined comments in each implementation.
class Solution {
public String customSortString(String S, String T) {
// count[char] = the number of occurrences of 'char' in T.
// This is offset so that count[0] = occurrences of 'a', etc.
// 'count' represents the current state of characters
// (with multiplicity) we need to write to our answer.
int[] count = new int[26];
for (char c: T.toCharArray())
count[c - 'a']++;
// ans will be our final answer. We use StringBuilder to join
// the answer so that we more efficiently calculate a
// concatenation of strings.
StringBuilder ans = new StringBuilder();
// Write all characters that occur in S, in the order of S.
for (char c: S.toCharArray()) {
for (int i = 0; i < count[c - 'a']; ++i)
ans.append(c);
// Setting count[char] to zero to denote that we do
// not need to write 'char' into our answer anymore.
count[c - 'a'] = 0;
}
// Write all remaining characters that don't occur in S.
// That information is specified by 'count'.
for (char c = 'a'; c <= 'z'; ++c)
for (int i = 0; i < count[c - 'a']; ++i)
ans.append(c);
return ans.toString();
}
}
他这个写法有点意思, 最后一个训话没有专门判断count是否大于0: 如果是0, 反正不会执行;
public String customSortString(String S, String T) {
int[] count = new int[26];
for (char c : T.toCharArray()) { ++count[c - 'a']; } // count each char in T.
StringBuilder sb = new StringBuilder();
for (char c : S.toCharArray()) {
while (count[c - 'a']-- > 0) { sb.append(c); } // sort chars both in T and S by the order of S.
}
for (char c = 'a'; c <= 'z'; ++c) {
while (count[c - 'a']-- > 0) { sb.append(c); } // group chars in T but not in S.
}
return sb.toString();
}
还是一样的意思;
https://leetcode.com/problems/custom-sort-string/discuss/116556/Two-Lines-C++
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;
}
};
这个方法不好, 这个find可能很慢; 最好还是自己做一个反向lookup;
The second Edition. It is easier to understand.
class Solution {
public:
string customSortString(string S, string T) {
unordered_map<char, int> dir;
for (int i = 0; i < S.size(); i++) {
dir[S[i]] = i + 1;
}
sort(T.begin(), T.end(),
[&](char a, char b) { return dir[a] < dir[b]; });
return T;
}
};
这个就是了;
we also can use stl
class Solution {
public:
string customSortString(string S, string T) {
unordered_map<char, int> dir;
int i = 0;
transform(S.begin(), S.end(), inserter(dir, dir.end()),
[&](char &a) { return make_pair(a, ++i); });
sort(T.begin(), T.end(),
[&](char a, char b) { return dir[a] < dir[b]; });
return T;
}
};
感觉还是类似的东西, c++的STL不太熟悉, 懒得看了;
Actually, this problem has two follow up questions:
Follow up 1: If the custom order S is too large, how to solve it efficiently?
Follow up 2: If the string T is too large, how to solve it efficiently?
这个还真的是没有想到?
第一问的意思, 估计是假设不限定全是小写字母了, 无重复估计还是可以限定的; 那么可以先走一遍T, 然后在S里面找到所有T的元素对应的位置, 然后从S的开头开始, 把这些找到的位置的数字, 一个一个的往前swap; 如果这个数字在T当中实际上是有多个copy, 就多swap几次就行了; 在S当中找T数字的过程, 可以用binary search来做, 因为没有重复, 所以固定的可以知道这个数字肯定在S的某一个位置; 以前总结过, binary search有对value search和对index search, 这里这个就是对index search;
T很大好像就真没什么好办法;
https://leetcode.com/problems/custom-sort-string/discuss/116512/Java8-3-lines-solution
The idea is to store the order of characters in S, in a map using their indexes. Then we can sort the string T using a comparator that is based on the indexes stored in the map.
public static String customSortString(String S, String T) {
Map<Character, Integer> map = new HashMap<>();
IntStream.range(0, S.length()).forEach(i -> map.put(S.charAt(i), i));
return T.chars().mapToObj(i -> (char)i)
.sorted(comparingInt(ch -> map.getOrDefault(ch, 0)))
.map(c -> String.valueOf((char)c))
.collect(joining());
}
这个跟上面那个c++的做法是一样的;
没有submission;
Problem Description
Problem Description
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"
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:
- S has length at most 26, and no character is repeated in S.
- T has length at most 200.
- S and T consist of lowercase letters only.
Difficulty:Medium
Total Accepted:1.1K
Total Submissions:1.7K
Contributor:awice