De-Optimized 469ms Dynamic Programming Solution


  • -1
    J

    Many coders have provided the O<N, 1> 2-pointer solution.

    I am so bored so I came up with a dynamic programming solution for this problem.

    The recurrence is:

    dp(s, t) = dp(s, t-1) or ( S[s] = T[t] and dp(s-1, t-1) )

    Base case:

    dp(0, t) = true
    dp(s, 0) = (s == "")

    The complexity is O(N^2, N) lol

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            int sl = s.length();
            int tl = t.length();
            boolean [] dp = new boolean[sl+1];
            
            for(int i = 0; i <= tl; i ++) {
                for(int j = sl; j >= 0; j --) {
                    if(j == 0) {
                        dp[j] = true;
                        continue;
                    }
                    
                    if(i == 0) {
                        dp[j] = (j == 0);
                        continue;
                    }
                    
                    dp[j] = dp[j] || (s.charAt(j-1) == t.charAt(i-1)) && dp[j-1];
                }
            }
            
            return dp[sl];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.