Solution share: DP and 2-pointer traversal


  • 0

    At first I wanted to DP to solve this problem:

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            return helper(s, t);
        }
        public boolean helper (String check, String dict) {
            if (check.length() == 0) return true; 
            if (check.length() > dict.length()) return false; 
            if (check.charAt(0) == dict.charAt(0)) {
                return helper(check.substring(1), dict.substring(1)); 
            } else {
                return helper(check, dict.substring(1)); 
            }
        }
    }
    

    However in thsi problem, DP solution causes stack overflow if the character we want to find in s is at the very end of t, while t is a very long string. And thus simply using two pointers to record the current position in s and t and traverse s and t would be better to solve this problem:

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            if (s.length() == 0) return true; 
            if (s.length() > t.length()) return false; 
            int index_s= 0, index_t = 0; 
            while (index_s < s.length() && index_t < t.length()) {
                if (s.charAt(index_s) == t.charAt(index_t)) {
                    index_s++; 
                }
                index_t++; 
            }
            return index_s == (s.length());
        }
    }
    

Log in to reply
 

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