Shortest Common Supersequence | Leetcode 1092

class Solution {
    string findLCS(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        string lcs;
        int i = len1, j = len2;
        while (i > 0 && j > 0) {
            if (str1[i-1] == str2[j-1]) {
                lcs.push_back(str1[i-1]);
                --i;
                --j;
            } else if (dp[i-1][j] > dp[i][j-1]) {
                --i;
            } else {
                --j;
            }
        }
        reverse(lcs.begin(), lcs.end());
        return lcs;
    }
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string ans = "";
        string lcs = findLCS(str1,str2);
        
        int p1=0,p2=0;
        for(char c: lcs)
        {
            while(str1[p1]!=c)  //Add all non-LCS chars from str1
                ans += str1[p1++];
            while(str2[p2]!=c)  //Add all non-LCS chars from str2
                ans += str2[p2++];
            
            ans += c;   //Add LCS-char and increment both ptrs
            ++p1;
            ++p2;
        }
        ans += str1.substr(p1) + str2.substr(p2);
        return ans;
    }
};
/*
//JAVA
class Solution {
    private String findLCS(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        // Build the DP table for LCS
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // Reconstruct the LCS from the DP table
        StringBuilder lcs = new StringBuilder();
        int i = len1, j = len2;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        // Reverse to get the correct order
        return lcs.reverse().toString();
    }
    
    public String shortestCommonSupersequence(String str1, String str2) {
        StringBuilder ans = new StringBuilder();
        String lcs = findLCS(str1, str2);
        
        int p1 = 0, p2 = 0;
        for (char c : lcs.toCharArray()) {
            // Add all non-LCS characters from str1
            while (p1 < str1.length() && str1.charAt(p1) != c) {
                ans.append(str1.charAt(p1++));
            }
            // Add all non-LCS characters from str2
            while (p2 < str2.length() && str2.charAt(p2) != c) {
                ans.append(str2.charAt(p2++));
            }
            // Add the LCS character
            ans.append(c);
            p1++;
            p2++;
        }
        
        // Add remaining characters from str1 and str2
        ans.append(str1.substring(p1));
        ans.append(str2.substring(p2));
        return ans.toString();
    }
}

#Python
class Solution:
    def findLCS(self, str1: str, str2: str) -> str:
        len1, len2 = len(str1), len(str2)
        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        
        # Build the DP table for LCS
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # Reconstruct the LCS from the DP table
        lcs = []
        i, j = len1, len2
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                lcs.append(str1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
        
        # Reverse to get the correct order
        lcs.reverse()
        return ''.join(lcs)
    
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        ans = []
        lcs = self.findLCS(str1, str2)
        
        p1, p2 = 0, 0
        for c in lcs:
            # Add all non-LCS characters from str1
            while p1 < len(str1) and str1[p1] != c:
                ans.append(str1[p1])
                p1 += 1
            # Add all non-LCS characters from str2
            while p2 < len(str2) and str2[p2] != c:
                ans.append(str2[p2])
                p2 += 1
            # Add the LCS character
            ans.append(c)
            p1 += 1
            p2 += 1
        
        # Add remaining characters from str1 and str2
        ans.append(str1[p1:])
        ans.append(str2[p2:])
        return ''.join(ans)
*/

why are we looking at comparing (i-1)==(j-1) not (i==j)