Shortest Common Subsequence using Dynamic Programming

This is a C++ Program that Solves Shortest Common Subsequence Problem using Dynamic Programming technique.

Problem Description

You are given two strings. Find the length of the shortest string that has both the given strings as subsequences.

Problem Solution

We can solve this problem by using bottom up DP. We will process the strings character by character and store the results for every pair of prefixes of string 1 and string 2.

Expected Input and Output

Case-1:

string 1 - APQRSTU
string 2 - KPLRMNTUO
 
length of shortest string that has both the given strings - 12 (AKPQLRSMNTUO)

Program/Source Code

Here is source code of the C++ Program to Solve Shortest Common Subsequence Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<string>
```
```
 
```
```
using namespace std;
```
```
 
```

int shortestCommonSubseq(string str1, string str2)

```
{
```

    int len1=str1.length(), len2=str2.length();

```
 
```
```
    int i,j,k;
```
```
 
```
```
    int dp[len1+1][len2+1];
```
```
 
```
```
    //initialization
```
```
    for(i=0;i<=len1;i++)
```
```
        dp[i][0]=i;
```
```
 
```
```
    for(j=1;j<=len2;j++)
```
```
        dp[0][j]=j;
```
```
 
```
```
    for(i=1;i<=len1;i++)
```
```
    {
```
```
        for(j=1;j<=len2;j++)
```
```
        {
```
```
            //match
```
```
            if(str1[i-1]==str2[j-1])
```
```
            {
```

                dp[i][j]=dp[i-1][j-1]+1;

```
            }
```
```
 
```
```
            //mismatch
```
```
            else
```
```
            {
```

                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;

```
            }
```
```
 
```
```
        }
```
```
    }
```
```
 
```
```
    return dp[len1][len2];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    string str1,str2;
```
```
 
```
```
    cout<<"Enter string 1  ";
```
```
    getline(cin,str1);
```
```
 
```
```
    cout<<"Enter string 2  ";
```
```
    getline(cin,str2);
```
```
 
```

    cout<<"Length of the shortest common subsequence is "<<endl;

    cout<<shortestCommonSubseq(str1,str2);

```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we will take input for str1 and str2. We will pass these to the function shortestCommonSubsequence as parameters. This function will calculate the result using bottom up DP and return the value which is displayed on the standard output.

Runtime Test Cases

 
Case-1:
$ g++ shortest_common_subsequence.cpp
$ ./a.out
Enter string 1 PQAMGBMCDKE
Enter string 2 ACBACPDE
Length of the shortest common subsequence is 
14

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Note: Join free Sanfoundry classes at Telegram or Youtube

« Prev - Count Number of Ways to Reach a Given Score Problem

» Next - Minimum Number of Squares Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: