Java 中自定义字符串排序

给定两个字符串 a1 和 a2。字符串 a1 的所有字符都是唯一的，并且按特定顺序排序。我们的任务是排列字符串 a2 的字符，使得字符串 a1 中字符出现的顺序在 a2 中也出现。字符串 a2 可以有许多有效的排列。返回字符串 a2 的任何一个有效排列。

示例 1

输入

字符串 a1 = "ktrmps" 字符串 a2 = "stkmoorp"

输出: "ktrmpsoo"

解释: 在字符串 a1 中，我们看到字符 'k' 首先出现。之后是字符 't'，然后是 'r'，然后是 'm'，然后是 'p'，最后是 's'。然而，字符串 a2 中并没有出现相同的顺序。因此，我们排列字符串 a2，得到 "ktrmpsoo"。在这个字符串中，顺序与字符串 a1 相同。因此，"ktrmpsoo" 是我们的答案。

示例 2

输入

字符串 a1 = "erhdqo" 字符串 a2 = "wwdybr"

输出: "rdwwyb"

解释: 在字符串 a1 中，我们看到字符 'e' 首先出现。之后是字符 'r'，然后是 'h'，然后是 'd'，然后是 'q'，最后是 'o'。然而，字符串 a2 中并没有出现相同的顺序。因此，我们排列字符串 a2，得到 "rdwwyb"。在这个字符串中，顺序与字符串 a1 相同。因此，"rdwwyb" 是我们的答案。请注意，"rdybww" 或 "rdbwwy" 也是有效的排列。

示例 3

输入

字符串 a1 = "abcd" 字符串 a2 = "efgh"

输出: "efgh"

解释: 字符串 a2 中没有字符与字符串 a1 中的字符匹配。因此，不需要排列。这样，我们可以将字符串 a2 作为我们的答案。

朴素方法

朴素方法是使用两个嵌套循环。外层循环遍历字符串 a1，内层循环遍历字符串 a2。内层循环检查外层循环变量指向的字符是否存在于字符串 a2 中。如果存在，则将其追加到名为 _answer_ 的字符串中。请注意，该字符串的所有出现都会被追加并从字符串中移除。最后，我们返回 _answer_。

文件名: CustomSortString.java

输出

For the strings "trmps" and "stkmoorp", the permuted string is: "trmpskoo"

For the strings "erhdqo" and "wwdybr", the permuted string is: "rdwwyb"

For the strings "abcd" and "efgh", the permuted string is: "efgh"

复杂度分析: 在最坏情况下，字符串 a2 中不会删除任何字符。因此，在每次外层循环迭代中，字符串 a2 的大小保持不变。正是由于这个原因，程序的时间复杂度为 O(M x N)，其中 M 是字符串 a1 中的总字符数，N 是字符串 a2 中的总字符数。该程序不使用任何额外空间，因此空间复杂度为 O(1)。

现在，我们将进行一些优化以降低程序的时间复杂度。

方法: 使用字符计数

为了获得线性时间复杂度，我们将计算字符在字符串 a2 中出现的次数，并将其存储在一个数组中（在本例中为 tempArr[]）。然后，遍历字符串 a1，并根据字符串 a1 中字符的排列顺序，使用 tempArr[] 构造结果字符串。遍历 tempArr[] 以将字符串 a2 的剩余字符追加到结果字符串中。请参阅以下程序。

文件名: CustomSortString1.java

输出

For the strings "trmps" and "stkmoorp", the permuted string is: "trmpskoo"

For the strings "erhdqo" and "wwdybr", the permuted string is: "rdbwwy"

For the strings "abcd" and "efgh", the permuted string is: "efgh"

复杂度分析: 该程序使用了嵌套的 for 循环。但是，这不会使程序的时间复杂度达到 O(M x N)。这是因为如果字符串 a1 中的字符不存在于字符串 a2 中，则内层循环将不起作用。该循环最多会遍历 O(N) 次。因此，程序的时间复杂度为 O(M + N)，其中 M 是字符串 a1 的大小，N 是字符串 a2 的大小。T

该程序使用了数组 bucketArr[]。但是，bucketArr[] 的大小是固定的。因此，使程序空间复杂度恒定，即 O(1)。