ENIGMA03 - Editorial

dynamic-programming
easy-medium
editorial
engm2015

#1

PROBLEM LINK:

Cut and Paste

Author and Editorialist : Vishal Sharma

DIFFICULTY:

Easy-Medium

PREREQUISITES:

DP

EXPLANATION:

Brute force approach

Time complexity - O( |str1| * |str2| )

Result – time limit exceeded

First, check whether all characters in str2 are also present in str1. If not, it is impossible to obtain str2 using str1.
Then, write a nested loop to search each character of str2 in str1.

Dynamic programming solution

time complexity – O( |s1|*26 + |s2|)

First create a matrix l[|s1+1|][256]

l*[j]=first occurrence of character j in the string s1[i…|s1|-1]

if j is not present in the s1[i…|s1-1|], l*[j]=|s1|

if (s1* == j)
l*[j] = i;

else if (i + 1 < n1)
l*[j] = l[i + 1][j];

SOLUTION

DP Solution Link