# 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.

Note: Join free Sanfoundry classes at Telegram or Youtube
1. #include<iostream>
2. #include<string>
3.
4. using namespace std;
5.
6. int shortestCommonSubseq(string str1, string str2)
7. {
8.     int len1=str1.length(), len2=str2.length();
9.
10.     int i,j,k;
11.
12.     int dp[len1+1][len2+1];
13.
14.     //initialization
15.     for(i=0;i<=len1;i++)
16.         dp[i][0]=i;
17.
18.     for(j=1;j<=len2;j++)
19.         dp[0][j]=j;
20.
21.     for(i=1;i<=len1;i++)
22.     {
23.         for(j=1;j<=len2;j++)
24.         {
25.             //match
26.             if(str1[i-1]==str2[j-1])
27.             {
28.                 dp[i][j]=dp[i-1][j-1]+1;
29.             }
30.
31.             //mismatch
32.             else
33.             {
34.                 dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
35.             }
36.
37.         }
38.     }
39.
40.     return dp[len1][len2];
41. }
42.
43. int main()
44. {
45.     string str1,str2;
46.
47.     cout<<"Enter string 1  ";
48.     getline(cin,str1);
49.
50.     cout<<"Enter string 2  ";
51.     getline(cin,str2);
52.
53.     cout<<"Length of the shortest common subsequence is "<<endl;
54.     cout<<shortestCommonSubseq(str1,str2);
55.
56.     cout<<endl;
57.     return 0;
58. }
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.