Check if a String is Subsequence of Other

PHOTO EMBED

Tue Feb 08 2022 10:29:13 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #string #subsequence

// Iterative Solution : Time Complexity : O(n+m), Space Complexity : Θ(1)

    static boolean isSubSeq(String s1, String s2, int n, int m){
        int j = 0;
        for(int i = 0; i < n && j < m; i++){
            if(s1.charAt(i) == s2.charAt(j))
            j++;
        }
        
        return j == m;
    }



// Recursive Solution : Time Complexity : O(n+m), Space Complexity : Θ(n+m)

    static boolean isSubSeq(String s1, String s2, int n, int m){
        if( m == 0 )
            return true;
        
        if( n == 0 )
            return false;
            
        if ( s1.charAt(n-1) == s2.charAt(m-1) )
            return isSubSeq(s1, s2, n-1, m-1);
        
        else
            return isSubSeq(s1, s2, n-1, m);
    }
content_copyCOPY

Input : ------- 6 3 ABCDEF ABD Output : --------- true