CODEWITHSUNDEEP
algorithmstring-matching
didxga
didxga

Reputation: 6125

Algorithm explanation for common strings

The Problem definition:

Given two strings a and b of equal length, what’s the longest string (S) that can be constructed such that S is a child to both a and b. String x is said to be a child of string y if x can be formed by deleting 0 or more characters from y

Input format

Two strings a and b with a newline separating them

Constraints

All characters are upper-cased and lie between ascii values 65-90 The maximum length of the strings is 5000

Output format

Length of the string S

Sample Input #0

HARRY SALLY

Sample Output #0

2

The longest possible subset of characters that is possible by deleting zero or more characters from HARRY and SALLY is AY, whose length is 2.

The solution:

public class Solution {
  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    char[] a = in.readLine().toCharArray();
    char[] b = in.readLine().toCharArray();
    int[][] dp = new int[a.length + 1][b.length + 1];
    dp[0][0] = 1;
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < b.length; j++)
           if (a[i] == b[j])
              dp[i + 1][j + 1] = dp[i][j] + 1;
           else
              dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
              System.out.println(dp[a.length][b.length]);
  }
}

Anyone has encountered this problem and solved using the solution like this? I solved it in a different way. Only found this solution is elegant, But can not make sense of it so far. Could anyone help explaining it little bit.

Upvotes: 2

Views: 1519

Answers (1)

grc
grc

Reputation: 786

This algorithm uses Dynamic Programming. The key point in understanding dynamic programming is to understand the recursive step which in this case is within the if-else statement. My understanding about the matrix of size (a.length+1) * (b.length +1) is that for a given element in the matrix dp[i +1, j +1] it represents that if the we only compare string a[0:i] and b[0:j] what will be the child of both a[0:i] and b[0:j] that has most characters.

So to understand the recursive step, let's look at the example of "HARRY" and "SALLY", say if I am on the step of calculating dp[5][5], in this case, I will be looking at the last character 'Y':

A. if a[4] and b[4] are equal, in this case "Y" = "Y", then i know the optimal solution is: 1) Find out what is the child of "HARR" and "SALL" that has most characters (let's say n characters) and then 2) add 1 to n.

B. if a[4] and b[4] are not equal, then the optimal solution is either Child of "HARR" and "SALLY" or Child of "HARRY" and "SALL" which will translate to Max(dp[i+1][j] and dp[i][j+1]) in the code.

Upvotes: 2

Related Questions