给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
提示：
登录
n == nums.length1 <= n <= 300nums[i] 为 0、1 或 2
进阶：
public void sortColors(int[] nums) {
int n0 = 0, n1 = 0;
for(int i = 0; i < nums.length; i++){
int num = nums[i];
nums[i] = 2;
if(num < 2){
nums[n1++] = 1;
}
if(num < 1){
nums[n0++] = 0;
}
}
}
本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。
根据题目中的提示，我们可以统计出数组中 $0, 1, 2$ 的个数，再根据它们的数量，重写整个数组。这种方法较为简单，也很容易想到，而本题解中会介绍两种基于指针进行交换的方法。
思路与算法
我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 $0$ 交换到数组的头部。在第二次遍历中，我们将数组中所有的 $1$ 交换到头部的 $0$ 之后。此时，所有的 $2$ 都出现在数组的尾部，这样我们就完成了排序。
具体地，我们使用一个指针 $\textit{ptr}$ 表示「头部」的范围，$\textit{ptr}$ 中存储了一个整数，表示数组 $\textit{nums}$ 从位置 $0$ 到位置 $\textit{ptr}-1$ 都属于「头部」。$\textit{ptr}$ 的初始值为 $0$，表示还没有数处于「头部」。
在第一次遍历中，我们从左向右遍历整个数组，如果找到了 $0$，那么就需要将 $0$ 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 $0$ 都被交换到「头部」的范围，并且「头部」只包含 $0$。
在第二次遍历中，我们从「头部」开始，从左向右遍历整个数组，如果找到了 $1$，那么就需要将 $1$ 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 $1$ 都被交换到「头部」的范围，并且都在 $0$ 之后，此时 $2$ 只出现在「头部」之外的位置，因此排序完成。
代码
###C++
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int ptr = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == 0) {
swap(nums[i], nums[ptr]);
++ptr;
}
}
for (int i = ptr; i < n; ++i) {
if (nums[i] == 1) {
swap(nums[i], nums[ptr]);
++ptr;
}
}
}
};
###Java
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int ptr = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == 0) {
int temp = nums[i];
nums[i] = nums[ptr];
nums[ptr] = temp;
++ptr;
}
}
for (int i = ptr; i < n; ++i) {
if (nums[i] == 1) {
int temp = nums[i];
nums[i] = nums[ptr];
nums[ptr] = temp;
++ptr;
}
}
}
}
###Python
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
ptr = 0
for i in range(n):
if nums[i] == 0:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
for i in range(ptr, n):
if nums[i] == 1:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
###Golang
func swapColors(colors []int, target int) (countTarget int) {
for i, c := range colors {
if c == target {
colors[i], colors[countTarget] = colors[countTarget], colors[i]
countTarget++
}
}
return
}
func sortColors(nums []int) {
count0 := swapColors(nums, 0) // 把 0 排到前面
swapColors(nums[count0:], 1) // nums[:count0] 全部是 0 了，对剩下的 nums[count0:] 把 1 排到前面
}
###C
void swap(int *a, int *b) {
int t = *a;
*a = *b, *b = t;
}
void sortColors(int *nums, int numsSize) {
int ptr = 0;
for (int i = 0; i < numsSize; ++i) {
if (nums[i] == 0) {
swap(&nums[i], &nums[ptr]);
++ptr;
}
}
for (int i = ptr; i < numsSize; ++i) {
if (nums[i] == 1) {
swap(&nums[i], &nums[ptr]);
++ptr;
}
}
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。
空间复杂度：$O(1)$。
思路与算法
方法一需要进行两次遍历，那么我们是否可以仅使用一次遍历呢？我们可以额外使用一个指针，即使用两个指针分别用来交换 $0$ 和 $1$。
具体地，我们用指针 $p_0$ 来交换 $0$，$p_1$ 来交换 $1$，初始值都为 $0$。当我们从左向右遍历整个数组时：
如果找到了 $1$，那么将其与 $\textit{nums}[p_1]$ 进行交换，并将 $p_1$ 向后移动一个位置，这与方法一是相同的；
如果找到了 $0$，那么将其与 $\textit{nums}[p_0]$ 进行交换，并将 $p_0$ 向后移动一个位置。这样做是正确的吗？我们可以注意到，因为连续的 $0$ 之后是连续的 $1$，因此如果我们将 $0$ 与 $\textit{nums}[p_0]$ 进行交换，那么我们可能会把一个 $1$ 交换出去。当 $p_0 < p_1$ 时，我们已经将一些 $1$ 连续地放在头部，此时一定会把一个 $1$ 交换出去，导致答案错误。因此，如果 $p_0 < p_1$，那么我们需要再将 $\textit{nums}[i]$ 与 $\textit{nums}[p_1]$ 进行交换，其中 $i$ 是当前遍历到的位置，在进行了第一次交换后，$\textit{nums}[i]$ 的值为 $1$，我们需要将这个 $1$ 放到「头部」的末端。在最后，无论是否有 $p_0 < p_1$，我们需要将 $p_0$ 和 $p_1$ 均向后移动一个位置，而不是仅将 $p_0$ 向后移动一个位置。
<,,,,,,,,,,,,,,,,,>
代码
###C++
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0, p1 = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == 1) {
swap(nums[i], nums[p1]);
++p1;
} else if (nums[i] == 0) {
swap(nums[i], nums[p0]);
if (p0 < p1) {
swap(nums[i], nums[p1]);
}
++p0;
++p1;
}
}
}
};
###Java
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int p0 = 0, p1 = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == 1) {
int temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
++p1;
} else if (nums[i] == 0) {
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
if (p0 < p1) {
temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
++p0;
++p1;
}
}
}
}
###Python
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0 = p1 = 0
for i in range(n):
if nums[i] == 1:
nums[i], nums[p1] = nums[p1], nums[i]
p1 += 1
elif nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
if p0 < p1:
nums[i], nums[p1] = nums[p1], nums[i]
p0 += 1
p1 += 1
###Golang
func sortColors(nums []int) {
p0, p1 := 0, 0
for i, c := range nums {
if c == 0 {
nums[i], nums[p0] = nums[p0], nums[i]
if p0 < p1 {
nums[i], nums[p1] = nums[p1], nums[i]
}
p0++
p1++
} else if c == 1 {
nums[i], nums[p1] = nums[p1], nums[i]
p1++
}
}
}
###C
void swap(int *a, int *b) {
int t = *a;
*a = *b, *b = t;
}
void sortColors(int *nums, int numsSize) {
int p0 = 0, p1 = 0;
for (int i = 0; i < numsSize; ++i) {
if (nums[i] == 1) {
swap(&nums[i], &nums[p1]);
++p1;
} else if (nums[i] == 0) {
swap(&nums[i], &nums[p0]);
if (p0 < p1) {
swap(&nums[i], &nums[p1]);
}
++p0;
++p1;
}
}
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。
空间复杂度：$O(1)$。
思路与算法
与方法二类似，我们也可以考虑使用指针 $p_0$ 来交换 $0$，$p_2$ 来交换 $2$。此时，$p_0$ 的初始值仍然为 $0$，而 $p_2$ 的初始值为 $n-1$。在遍历的过程中，我们需要找出所有的 $0$ 交换至数组的头部，并且找出所有的 $2$ 交换至数组的尾部。
由于此时其中一个指针 $p_2$ 是从右向左移动的，因此当我们在从左向右遍历整个数组时，如果遍历到的位置超过了 $p_2$，那么就可以直接停止遍历了。
具体地，我们从左向右遍历整个数组，设当前遍历到的位置为 $i$，对应的元素为 $\textit{nums}[i]$；
如果找到了 $0$，那么与前面两种方法类似，将其与 $\textit{nums}[p_0]$ 进行交换，并将 $p_0$ 向后移动一个位置；
如果找到了 $2$，那么将其与 $\textit{nums}[p_2]$ 进行交换，并将 $p_2$ 向前移动一个位置。
这样做是正确的吗？可以发现，对于第二种情况，当我们将 $\textit{nums}[i]$ 与 $\textit{nums}[p_2]$ 进行交换之后，新的 $\textit{nums}[i]$ 可能仍然是 $2$，也可能是 $0$。然而此时我们已经结束了交换，开始遍历下一个元素 $\textit{nums}[i+1]$，不会再考虑 $\textit{nums}[i]$ 了，这样我们就会得到错误的答案。
因此，当我们找到 $2$ 时，我们需要不断地将其与 $\textit{nums}[p_2]$ 进行交换，直到新的 $\textit{nums}[i]$ 不为 $2$。此时，如果 $\textit{nums}[i]$ 为 $0$，那么对应着第一种情况；如果 $\textit{nums}[i]$ 为 $1$，那么就不需要进行任何后续的操作。
<,,,,,,,,,,,,>
代码
###C++
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0, p2 = n - 1;
for (int i = 0; i <= p2; ++i) {
while (i <= p2 && nums[i] == 2) {
swap(nums[i], nums[p2]);
--p2;
}
if (nums[i] == 0) {
swap(nums[i], nums[p0]);
++p0;
}
}
}
};
###Java
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int p0 = 0, p2 = n - 1;
for (int i = 0; i <= p2; ++i) {
while (i <= p2 && nums[i] == 2) {
int temp = nums[i];
nums[i] = nums[p2];
nums[p2] = temp;
--p2;
}
if (nums[i] == 0) {
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
++p0;
}
}
}
}
###Python
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0, p2 = 0, n - 1
i = 0
while i <= p2:
while i <= p2 and nums[i] == 2:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
if nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
p0 += 1
i += 1
###Golang
func sortColors(nums []int) {
p0, p2 := 0, len(nums)-1
for i := 0; i <= p2; i++ {
for ; i <= p2 && nums[i] == 2; p2-- {
nums[i], nums[p2] = nums[p2], nums[i]
}
if nums[i] == 0 {
nums[i], nums[p0] = nums[p0], nums[i]
p0++
}
}
}
###C
void swap(int *a, int *b) {
int t = *a;
*a = *b, *b = t;
}
void sortColors(int *nums, int numsSize) {
int p0 = 0, p2 = numsSize - 1;
for (int i = 0; i <= p2; ++i) {
while (i <= p2 && nums[i] == 2) {
swap(&nums[i], &nums[p2]);
--p2;
}
if (nums[i] == 0) {
swap(&nums[i], &nums[p0]);
++p0;
}
}
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。
空间复杂度：$O(1)$。
本题其实是经典的荷兰国旗问题，最初由荷兰计算机科学家艾兹赫尔·迪克斯特拉（Edsger W. Dijkstra）提出，并以荷兰国旗的颜色（红、白、蓝）为类比。
如果你学习过「快速排序」，知道「三路快排」，这道题就非常简单，本题考查的知识点就是「三路快排」。我以前录过视频讲解了「快速排序」：地址，在第 6 节讲到了「三路快排」。
容易想到的做法：
「快速排序」的 partition，其中有一种 partition 叫做「三路快排」，即通过一次 partition，把区间里的数根据基准元素 pivot 分成 3 个部分：
pivot；pivot；pivot。本题的解法和「三路快排」几乎是一样，在「一趟扫描」的过程中，使用变量 i 扫描，分别使用两个变量放在数组的头和尾，我们就分别命名为 zero 和 two。其中
zero 是 0 和 1 的分界；two 是 2 和还未遍历到的数的分界。变量的定义如下图所示（「参考代码 1」采用的定义方式）：
变量 i 看到 1 的时候直接 ++ ，看到 0 的时候交换到数组的前面，看到 2 的时候交换到数组的末尾。具体细节，可以先写出变量的定义，在编码就容易多了。
这里给出两版代码，其实是一样的，它们的区别仅仅在于 zero 指向 0 还是指向 1 ，two 指向 2 还是指向未看到的数。我们把 zero 和 two 的定义写成了区间的形式，写在注释中。
由于区间定义不同，初始化，循环过程中，退出循环的条件就有细微差别。
参考代码 1：
###java
public class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
if (n < 2) {
return;
}
// all in [0..zero) = 0
// all in [zero..i) = 1
// all in [two..n - 1] = 2
// 初始化的时候，要满足上面 3 个区间全是空区间
int zero = 0;
int two = n;
int i = 0;
// i = two 的时候，[zero..i)、[two..len - 1] 已经接起来了，所以 while 里面是 i < two
while (i < two) {
if (nums[i] == 0) {
// zero 指向 1，所以先交换
swap(nums, i, zero);
zero++;
i++;
} else if (nums[i] == 1) {
// 直接划分到 1 所在的区间
i++;
} else {
// [two..n - 1] = 2，two 指向 2，所以先 -- ，再交换
two--;
swap(nums, i, two);
}
}
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
复杂度分析：
参考代码 2：
###java
public class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
if (n < 2) {
return;
}
// all in [0, zero] = 0
// all in (zero, i) = 1
// all in (two, n - 1] = 2
int zero = -1;
int two = n - 1;
int i = 0;
while (i <= two) {
if (nums[i] == 0) {
zero++;
swap(nums, i, zero);
i++;
} else if (nums[i] == 1) {
i++;
} else {
swap(nums, i, two);
two--;
}
}
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
复杂度分析：（同「参考代码 1」）。
思路与算法
题目要求找到 $[0, 1, ..., n - 1]$ 中的最长子序列，该子序列中满足前后相邻下标对应的 $\textit{groups}$ 值不同，且相邻下标对应的 $\textit{words}$ 的汉明距离为 $1$。与「最长相邻不相等子序列 I」题目类似，我们仍可采用动态规划来解决该问题。
设 $\textit{dp}[i]$ 表示以下标 $i$ 为结尾的最长子序列长度，设 $\text{HammingDistance}(s,t)$ 表示两个字符串 $s,t$ 的「汉明距离」。子序列中如果下标 $i$ 可以添加在下标 $j$ 之后，则此时一定满足 $\textit{groups}[i] \neq \textit{groups}[j], j < i$ 且 $\text{HammingDistance}(\textit{words}[i], \textit{words}[j]) = 1$，此时下标 $i$ 可以添加到下标 $j$ 之后，此时以下标 $i$ 为结尾的最长子序列长度为 $\textit{dp}[i] = \textit{dp}[j] + 1$，我们可以得到动态规划递推公式如下：
$$
\textit{dp}[i] = \max(\textit{dp}[i], \textit{dp}[j] + 1) \quad if \quad \textit{groups}[i] \neq \textit{groups}[j],\text{HammingDistance}(\textit{words}[i], \textit{words}[j]) = 1
$$
对于下标 $i$，我们可以枚举 $i$ 之前的小标，即可求得以 $i$ 为结尾的最长子序列的长度，依次求出以每个下标为结尾的最长子序列长度即可找到 $[0, 1, ..., n - 1]$
中的最长子序列长度。为了方便计算，我们用 $\textit{prev}[i]$ 记载以下标 $i$ 为结尾的最长子序列中 $i$ 的上一个下标。当我们找到最长子序列的结尾下标 $i$ 时，沿着 $i$ 往前即可找到整个序列的下标，并将每个下标对应的字符串加入到数组中，对整个数组反转后的结果即为答案。
代码
###C++
class Solution {
public:
vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
int n = groups.size();
vector<int> dp(n, 1);
vector<int> prev(n, -1);
int maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (check(words[i], words[j]) == 1 && dp[j] + 1 > dp[i] && groups[i] != groups[j]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
vector<string> ans;
for (int i = maxIndex; i >= 0; i = prev[i]) {
ans.emplace_back(words[i]);
}
reverse(ans.begin(), ans.end());
return ans;
}
bool check(string &s1, string &s2) {
if (s1.size() != s2.size()) {
return false;
}
int diff = 0;
for (int i = 0; i < s1.size(); i++) {
diff += s1[i] != s2[i];
if (diff > 1) {
return false;
}
}
return diff == 1;
}
};
###Java
class Solution {
public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
int n = groups.length;
int[] dp = new int[n];
int[] prev = new int[n];
Arrays.fill(dp, 1);
Arrays.fill(prev, -1);
int maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (check(words[i], words[j]) && dp[j] + 1 > dp[i] && groups[i] != groups[j]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
List<String> ans = new ArrayList<>();
for (int i = maxIndex; i >= 0; i = prev[i]) {
ans.add(words[i]);
}
Collections.reverse(ans);
return ans;
}
private boolean check(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
int diff = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
if (++diff > 1) {
return false;
}
}
}
return diff == 1;
}
}
###C#
public class Solution {
public IList<string> GetWordsInLongestSubsequence(string[] words, int[] groups) {
int n = groups.Length;
int[] dp = new int[n];
int[] prev = new int[n];
Array.Fill(dp, 1);
Array.Fill(prev, -1);
int maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (Check(words[i], words[j]) && dp[j] + 1 > dp[i] && groups[i] != groups[j]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
List<string> ans = new List<string>();
for (int i = maxIndex; i >= 0; i = prev[i]) {
ans.Add(words[i]);
}
ans.Reverse();
return ans;
}
private bool Check(string s1, string s2) {
if (s1.Length != s2.Length) {
return false;
}
int diff = 0;
for (int i = 0; i < s1.Length; i++) {
if (s1[i] != s2[i]) {
if (++diff > 1) {
return false;
}
}
}
return diff == 1;
}
}
###Python
class Solution:
def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
n = len(groups)
dp = [1] * n
prev_ = [-1] * n
max_index = 0
for i in range(1, n):
for j in range(i):
if self.check(words[i], words[j]) and dp[j] + 1 > dp[i] and groups[i] != groups[j]:
dp[i] = dp[j] + 1
prev_[i] = j
if dp[i] > dp[max_index]:
max_index = i
ans = []
i = max_index
while i >= 0:
ans.append(words[i])
i = prev_[i]
ans.reverse()
return ans
def check(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2):
return False
diff = 0
for c1, c2 in zip(s1, s2):
if c1 != c2:
diff += 1
if diff > 1:
return False
return diff == 1
###Go
func getWordsInLongestSubsequence(words []string, groups []int) []string {
n := len(groups)
dp := make([]int, n)
prev := make([]int, n)
for i := range dp {
dp[i] = 1
prev[i] = -1
}
maxIndex := 0
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if check(words[i], words[j]) && dp[j]+1 > dp[i] && groups[i] != groups[j] {
dp[i] = dp[j] + 1
prev[i] = j
}
}
if dp[i] > dp[maxIndex] {
maxIndex = i
}
}
ans := []string{}
for i := maxIndex; i >= 0; i = prev[i] {
ans = append(ans, words[i])
}
reverse(ans)
return ans
}
func check(s1, s2 string) bool {
if len(s1) != len(s2) {
return false
}
diff := 0
for i := 0; i < len(s1); i++ {
if s1[i] != s2[i] {
diff++
if diff > 1 {
return false
}
}
}
return diff == 1
}
func reverse(arr []string) {
for i, j := 0, len(arr) - 1; i < j; i, j = i + 1, j - 1 {
arr[i], arr[j] = arr[j], arr[i]
}
}
###C
bool check(const char *s1, const char *s2) {
if (strlen(s1) != strlen(s2)) {
return false;
}
int diff = 0;
for (int i = 0; s1[i]; i++) {
if (s1[i] != s2[i]) {
if (++diff > 1) {
return false;
}
}
}
return diff == 1;
}
char **getWordsInLongestSubsequence(char **words, int wordsSize, int *groups, int groupsSize, int *returnSize) {
int *dp = (int *)malloc(wordsSize * sizeof(int));
int *prev = (int *)malloc(wordsSize * sizeof(int));
for (int i = 0; i < wordsSize; i++) {
dp[i] = 1;
prev[i] = -1;
}
int maxIndex = 0;
for (int i = 1; i < wordsSize; i++) {
for (int j = 0; j < i; j++) {
if (check(words[i], words[j]) && dp[j] + 1 > dp[i] && groups[i] != groups[j]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
int count = 0;
for (int i = maxIndex; i >= 0; i = prev[i]) {
count++;
}
char **ans = (char **)malloc(count * sizeof(char *));
int index = 0;
for (int i = maxIndex; i >= 0; i = prev[i]) {
ans[index++] = words[i];
}
for (int i = 0; i < count / 2; i++) {
char *temp = ans[i];
ans[i] = ans[count - 1 - i];
ans[count - 1 - i] = temp;
}
*returnSize = count;
free(dp);
free(prev);
return ans;
}
###JavaScript
var getWordsInLongestSubsequence = function(words, groups) {
const n = groups.length;
const dp = new Array(n).fill(1);
const prev = new Array(n).fill(-1);
let maxIndex = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (check(words[i], words[j]) && dp[j] + 1 > dp[i] && groups[i] !== groups[j]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
const ans = [];
for (let i = maxIndex; i >= 0; i = prev[i]) {
ans.push(words[i]);
}
ans.reverse();
return ans;
};
const check = (s1, s2) => {
if (s1.length !== s2.length) {
return false;
}
let diff = 0;
for (let i = 0; i < s1.length; i++) {
if (s1[i] !== s2[i]) {
if (++diff > 1) {
return false;
}
}
}
return diff === 1;
};
###TypeScript
function getWordsInLongestSubsequence(words: string[], groups: number[]): string[] {
const n = groups.length;
const dp = new Array(n).fill(1);
const prev = new Array(n).fill(-1);
let maxIndex = 0;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (check(words[i], words[j]) && dp[j] + 1 > dp[i] && groups[i] !== groups[j]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > dp[maxIndex]) {
maxIndex = i;
}
}
const ans = [];
for (let i = maxIndex; i >= 0; i = prev[i]) {
ans.push(words[i]);
}
ans.reverse();
return ans;
};
function check(s1: string, s2: string): boolean {
if (s1.length !== s2.length) {
return false;
}
let diff = 0;
for (let i = 0; i < s1.length; i++) {
if (s1[i] !== s2[i]) {
if (++diff > 1) {
return false;
}
}
}
return diff === 1;
}
###Rust
impl Solution {
pub fn get_words_in_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
let n = groups.len();
let mut dp = vec![1; n];
let mut prev = vec![-1; n];
let mut max_index = 0;
for i in 1..n {
for j in 0..i {
if Self::check(&words[i], &words[j]) && dp[j] + 1 > dp[i] && groups[i] != groups[j] {
dp[i] = dp[j] + 1;
prev[i] = j as i32;
}
}
if dp[i] > dp[max_index] {
max_index = i;
}
}
let mut ans = Vec::new();
let mut i = max_index as i32;
while i >= 0 {
ans.push(words[i as usize].clone());
i = prev[i as usize];
}
ans.reverse();
ans
}
fn check(s1: &String, s2: &String) -> bool {
if s1.len() != s2.len() {
return false;
}
let mut diff = 0;
for (c1, c2) in s1.chars().zip(s2.chars()) {
if c1 != c2 {
diff += 1;
if diff > 1 {
return false;
}
}
}
diff == 1
}
}
复杂度分析
时间复杂度：$O(n^2L)$，其中 $n$ 表示给定数组的长度，$L$ 表示字符串数组 $\textit{word}$ 中字符串的长度。计算两个字符串的汉明码距离需要的时间为 $L$，找到以索引 $i$ 为结尾的最长子序列的需要遍历 $i$ 之前的所有索引，此时需要的时间为 $O(nL)$，求出以每个索引为结尾的最长子序列长度此时需要总时间为 $O(n^2L)$。
空间复杂度：$O(n)$。其中 $n$ 表示给定数组的长度。需要存储以每个索引为结尾的最长子序列长度，一共需要的空间为 $O(n)$。
