算法练习

Question

我正在做这个算法练习，但我不完全理解这个公式。这是练习:

Given a string str and array of pairs that indicates which indices in the string can be swapped, return the lexicographically largest string that results from doing the allowed swaps. You can swap indices any number of times.

Example

For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be swapLexOrder(str, pairs) = "dbca".

By swapping the given indices, you get the strings: "cbda", "cbad", "dbac", "dbca". The lexicographically largest string in this list is "dbca".

Input/Output

[execution time limit] 4 seconds (js)

[input] string str

A string consisting only of lowercase English letters.

Guaranteed constraints: 1 ≤ str.length ≤ 104.

[input] array.array.integer pairs

An array containing pairs of indices that can be swapped in str (1-based). This means that for each pairs[i], you can swap elements in str that have the indices pairs[i][0] and pairs[i][1].

Guaranteed constraints: 0 ≤ pairs.length ≤ 5000, pairs[i].length = 2.

[output] string

我的问题是，为什么“abcd”不是一个可能的答案(只是交换原始字符串“abdc”上的索引 3 和 4)？这个例子说

By swapping the given indices, you get the strings: "cbda", "cbad", "dbac", "dbca". The lexicographically largest string in this list is "dbca"

我知道即使“abcd”是一个可能的答案，“dbca”在字典序上是最大的，所以答案是一样的。但如果我不明白为什么“abcd”不是一个可能的答案，我想我误解了任务

Answer 1

您正确阅读了问题，但他们的描述是错误的。 "abcd" 和 "abdc" 都在您可以生成的可能字符串列表中，但不在它们的列表中。