【POJ2192】Zipper(动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 22 日

这个题目要求判断2个字符串能否组成1个字符串,例如cat和tree能组成tcraete。我们定义一个布尔类型的二维数组 array,array[i][j]表示str1[i]和str2[j]能否组成str[i+j].i=0或者j=0表示空字符串,所以初始化时,array[0][j]表示str1的前j个字符是否和str都匹配。
对于str=tcraete:

  Null c a t
Null 1 0 0 0
t 1      
r 0      
e 0      
e 0      

可以证明:当array[i-1][j]( array[i][j]上面一格)和array[i][j-1]( array[i][j]左面一格)都为0时,array[i][j]为0.当array[i-1][j]( array[i][j]上面一格)为1且左面字母为str[i+j]时或者当array[i][j-1]( array[i][j]左面一格)为1且上面字母为str[i+j]时,array[i][j]为1.这就是状态转移方程为。

#include <iostream>  
#include <string>  
using namespace std;  
bool arr[202][202];  
int main(){  
    string st1,st2,st3;  
    int n;  
    cin>>n;  
    for(int x=1;x<=n;x++){  
        cin>>st1>>st2>>st3;  
        arr[0][0]=1;  
        for (int i=1;i<=st1.length();i++)  
            if(st3[i-1]==st1[i-1]) arr[i][0]=1;  
        for (int i=1;i<=st2.length();i++)  
            if(st3[i-1]==st2[i-1]) arr[0][i]=1;  
        for (int i=1;i<=st1.length();i++){  
            for (int j=1;j<=st2.length();j++){  
                if(arr[i][j-1]&&st2[j-1]==st3[i+j-1]||  
                arr[i-1][j]&&st1[i-1]==st3[i+j-1])  
                    arr[i][j] = true;  
                else  
                    arr[i][j] = false;  
            }  
        }  
        cout<<"Data set "<<x<<": "<<  
            ((arr[st1.length()][st2.length()]==1)?("yes"):("no"))  
            <<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日