Session 42: DP 4

Original Session

Date: 15 Feb 2025

Topic: DP

Concept:

Programs

1. 1092. Shortest Common Supersequence
   1. leetcode here

      public String shortestCommonSupersequence(String text1, String text2) {
              
              int n = text1.length();
              int m = text2.length();
      
              int[][] dp = new int[n+1][m+1];
              for (int i = 1; i<=n; i++) {
      
                  for (int j = 1; j<=m; j++) {
      
                      if (text1.charAt(i-1) == text2.charAt(j-1)) {
                          dp[i][j] = 1 + dp[i-1][j-1]; 
                      } else {
                          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                      }
                  }
              }
      
              StringBuilder sb = new StringBuilder();
      
              while (m>0 && n>0) {
      
                  if (text1.charAt(n-1) == text2.charAt(m-1)) {
                      sb.append(text1.charAt(n-1));
                      m--;
                      n--;
                  } else {
                      
                      if (dp[n-1][m] > dp[n][m-1]) {
                          sb.append(text1.charAt(n-1));
                          n--;
                      } else {
                          sb.append(text2.charAt(m-1));
                          m--;
                      }
                  }
              }
      
              while (n>0) {
                  sb.append(text1.charAt(n-1));
                  n--;
              }
              while (m>0) {
                  sb.append(text2.charAt(m-1));
                  m--;
              }
              return sb.reverse().toString();
          }

2. Printing Longest Common Subsequence
   1. GFG practice here

3. 72. Edit Distance
   1. leetcode here

      public int minDistance(String word1, String word2) {
              
              int n = word1.length();
              int m = word2.length();
      
              int[][] dp = new int[n+1][m+1];
              for (int i=0; i<=m; i++) {
                  dp[0][i] = i;
              }
              for (int i=0; i<=n; i++) {
                  dp[i][0] = i;
              }
      
              for (int i = 1; i<=n; i++) {
      
                  for (int j = 1; j<=m; j++) {
      
                      if (word1.charAt(i-1) == word2.charAt(j-1)) {
                          dp[i][j] = dp[i-1][j-1]; 
                      } else {
                          dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                      }
                  }
              }
              return dp[n][m];
          }

4. 44. Wildcard Matching [failing test case]
   1. leetcode here

      public boolean isMatch(String s, String p) {
              
              boolean[][] dp = new boolean[p.length()+1][s.length()+1];
      				
      				dp[0][0] = true;
              for (int i=1; i<p.length()+1; i++) {
      
                  if (p.charAt(i-1) == '*') {
                      dp[i][0] = dp[i-1][0];
                  }
              }
      
              for (int i=1; i<p.length() + 1; i++) {
      
                  for (int j=1; j<s.length() + 1; j++) {
      
                      if (p.charAt(i-1) == '*') {
      
                          dp[i][j] = dp[i-1][j] || dp[i][j-1];
                      } else {
      
                          if ((s.charAt(j-1) == p.charAt(i-1)) || p.charAt(i-1) == '?') {
      
                              dp[i][j] = dp[i-1][j-1];
                          }
                      }
                  }
              }
      
              return dp[p.length()][s.length()];
          }

5. 91. Deecode Ways
   1. leetcode here

      public int numDecodings(String s) {
              
              int[] dp = new int[s.length() + 1];
              dp[0] = 1;
              dp[1] = s.charAt(0) == '0' ? 0 : 1;
      
              for (int i=2; i<dp.length; i++) {
      
                  if (s.charAt(i-1) != '0') {
                      dp[i] = dp[i-1];
                  }
      
                  int twoDigit = Integer.valueOf(s.substring(i-2, i));
                  if (twoDigit >= 10 && twoDigit <= 26) {
      
                      dp[i] = dp[i] + dp[i-2];
                  }
              }
      
              return dp[s.length()];
          }

6. [HomeWork] 354. Russian Doll Envelopes
   1. leetcode here