编辑距离 一维数组 c++

### C++ 实现基于一维数组的编辑距离算法

为了计算两个字符串之间的最小编辑距离，可以采用动态规划的方法。通过优化空间复杂度，可以从二维数组简化为仅使用一维数组来存储中间状态。

对于给定的源字符串 `s` 和目标字符串 `t`，可以通过构建一个长度等于较短字符串长度的一维数组来进行迭代更新。每次处理新字符时，只需保留当前行和上一行的数据即可完成整个过程[^2]。

下面是具体的 C++ 代码实现：

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int minDistance(string word1, string word2) {
    int n = word1.length();
    int m = word2.length();

    if (n * m == 0)
        return n + m;

    vector<int> dp(m + 1);

    // 初始化dp数组的第一行为word2的前缀匹配代价
    for (int i = 0; i <= m; ++i)
        dp[i] = i;

    for (int i = 1; i <= n; ++i) {
        int pre = dp[0];
        dp[0] = i;
        
        for (int j = 1; j <= m; ++j) {
            int temp = dp[j];  // 记录即将被覆盖的位置
            
            if (word1[i - 1] == word2[j - 1])
                dp[j] = pre;
            else
                dp[j] = min(pre, min(dp[j], dp[j - 1])) + 1;
            
            pre = temp;
        }
    }

    return dp[m];
}

此版本的空间复杂度降低到了 O(min(n,m))，其中 n 是第一个字符串的长度而 m 是第二个字符串的长度。时间复杂度保持不变仍为 O(n*m)。