字符串的扩展距离问题

• 题目

对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其他字符的距离为一定值k。
在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。
算法要求如下
1、 数据输入：第1行是字符串A，第2行是字符串B，第3行是空格与其他字符的距离定值k。
2、 输出：字符串A和B的扩展距离。
例如
输入：
cmc
snmn
2
输出：10（下面的代码进行了扩展，能够输出最终的字符串）

• 分析

义一个二维数组val[i][j] 表示第一个字符串已经匹配到第i位，第二个字符串已经匹配到第j位时两者扩展距离的最小值，我们可以看到此时，val[i][j] 可能由三种情况得到，一种是i和j匹配时扩展距离加上两者的字符的距离dist，另一种是j和0到i-1中的某一位匹配，剩下i和空格匹配（或者是i和0~j-1中某一位匹配，j和空格匹配）此时扩展距离只要加上k就可以了 （https://blog.csdn.net/becky_w/article/details/79995770）

• 代码（C++）

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

string stra;
string strb;
int k;


int extendDistance(){
    int lenA = stra.length();
    int lenB = strb.length();
    int val[lenA+1][lenB+1];

    int flag[lenA+1][lenB+1];

    for(int i=0; i<=lenA; i++){//2表示val[i][j]=val[i][j-1]+k
        val[i][0]=k*i;
        flag[i][0]=2;
    }
    for(int j=0; j<=lenB; j++){//2表示val[i][j]=val[i-1][j]+k
        val[0][j]=k*j;
        flag[0][j]=1;
    }

    flag[0][0] = -1;


    for(int i=1; i<=lenA; i++){
        for(int j=1; j<=lenB; j++){
            int tmp1 = val[i-1][j] + k;
            int tmp2 = val[i][j-1] + k;
            int tmp3 = val[i-1][j-1]+abs(stra[i-1]-strb[j-1]);
            val[i][j]=min(min(tmp1,tmp2),tmp3);

            if(val[i][j] == tmp1){//2表示val[i][j]=val[i][j-1]+k
                flag[i][j]=2;
            }
            else if(val[i][j] == tmp2){//2表示val[i][j]=val[i-1][j]+k
                flag[i][j]=1;
            }
            else
                flag[i][j]=3;//3表示val[i][j]=val[i-1][j-1]+abs(stra[i-1]-strb[j-1])
        }
    }

    vector<int> route;//找出路径（倒序）
    int i=lenA;
    int j=lenB;
    while(flag[i][j]!=-1){
        route.push_back(flag[i][j]);
        if(flag[i][j]==3){
            i--;
            j--;
        }else if(flag[i][j]==2){
            i--;
        }else{
            j--;
        }
    }
    vector<char> _strA;//根据路径，拼接字符串
    vector<char> _strB;
    int indxA=0;
    int indxB=0;
    for(int i=route.size()-1; i>=0; i--){
        if(route[i]==1){
            _strA.push_back(' ');
            _strB.push_back(strb[indxB]);
            indxB++;
        }else if(route[i]==2){
            _strA.push_back(stra[indxA]);
            _strB.push_back(' ');
            indxA++;
        }else{
            _strA.push_back(stra[indxA]);
            _strB.push_back(strb[indxB]);
            indxA++;
            indxB++;
        }
    }

    cout<<"val[][]:"<<endl;
    for(int i=0; i<=lenA; i++){
        for(int j=0;j<=lenB; j++){
            cout<<val[i][j]<<" ";
        }
        cout<<endl;
    }

    cout<<"flag[][]:"<<endl;
    for(int i=0; i<=lenA; i++){
        for(int j=0;j<=lenB; j++){
            cout<<flag[i][j]<<" ";
        }
        cout<<endl;
    }

    cout<<"strA:"<<endl;
    for(int i=0;i<_strA.size(); i++){
        cout<<_strA[i];
    }

    cout<<endl<<"strB:"<<endl;
    for(int i=0;i<_strB.size(); i++){
        cout<<_strB[i];
    }

    return val[lenA][lenB];
}

int main(){
    cin>>stra>>strb>>k;
    stra = stra;
    strb = strb;
    cout<<endl<<extendDistance()<<endl;
    return 0;
}