Straight forward Java simple solution


  • 53
    S

    Just use two pointers:

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

  • 1
    Z

    The same idea:

    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        }
        int i = 0;
        
        for (int j = 0; j < t.length(); j++) {
            if (t.charAt(j) == s.charAt(i)) {
                i++;
            }
            if (i == s.length()) {
                return true;
            }
        }
        
        return false;
    }

  • 3

    C# - iterate through t and increment s if the current s matches t. If you exhaust t you have failed, if you exhaust s you have succeeded.

        public bool IsSubsequence(string s, string t) 
        {
            int count = 0;
            for (int i = 0; i < t.Length && count < s.Length; i++)
            {
                if (s[count] == t[i]) count++;
            }
            return count == s.Length;
        }
    

  • 0
    M
    This post is deleted!

  • 0
    M

    @jdrogin: Very nice and elegant solution!


  • 0

    Similar idea, but it runs faster.

        public boolean isSubsequence(String s, String t) {
            int index = -1; 
            for (int i = 0; i < s.length(); i++) {
                index = t.indexOf(s.charAt(i), index + 1); //feed back as the next offset
                if (index == -1) return false; 
            }
            return true; 
        }

  • 0

    Two pointers

    public class Solution {
        public bool IsSubsequence(string s, string t) {
            if (s == null || t == null) {
                return false;
            }
            
            int indexS = 0;
            int indexT = 0;
            
            while(indexS < s.Length && indexT < t.Length) {
                if (s[indexS] == t[indexT]) {
                    indexS++;
                }
                
                indexT++;
            }
            
            return indexS == s.Length;
        }
    }
    

  • 0

    @zzhai Similar solution in a slightly more compact form, with followup: https://discuss.leetcode.com/topic/84971/5-lines-of-java-beats-90-follow-up


  • 0

    Verbose but easy to understand. C# - 2 pointers

        public bool IsSubsequence(string s, string t)
        {
            if (string.IsNullOrEmpty(s))
                return true;
    
            int i = 0, j = 0;
            while (j < s.Length && i < t.Length)
            {
                if (t[i] == s[j])
                {
                    i++;
                    j++;
                }
                else  //t[i] != s[j]
                {
                    i++;
                }
            }
    
            return j == s.Length;
        }
    

  • 0
    F

    Do you have follow up solution?


  • 0

    Wonder how to analyze this solution's time complexity, since it depends on t and s conditionally, although O(t.length) is definitely correct ...how to give a more tight upper bound?


  • 0
        public boolean isSubsequence(String s, String t) {
          int m = s.length(), n = t.length();
          if(m > n) return false;
          
          char[] sc = s.toCharArray(), tc = t.toCharArray();
          int i = 0, j = 0;  
          while(i < m && j < n){
            if(sc[i] == tc[j]) i++;
            j++;  
          }  
          return i == m;  
        }

  • 0
    H

    @ZhuEason Cause you often post 01 pack solutions, when I first looked at this problem, I thought I could use 01 pack to solve this, which is really slow for this problem.

    public static boolean isSubsequence(String s, String t) {
            if(t.length() < s.length()){
                return false;
            }
            int m = s.length();
            int n = t.length();
            boolean[] dp = new boolean[n + 1];
            for(int i = 0; i <= n; i++){
            	dp[i] = true;
            }
            for(int i = 1; i <= m; i++){
            	boolean[] temp = new boolean[n + 1];
            	for(int j = 1; j <= n; j++){
            		temp[j] = temp[j - 1];
            		if(s.charAt(i - 1) == t.charAt(j - 1)){
            			temp[j] |= dp[j - 1];
            		}
            	}
            	dp = temp;
            }
            return dp[n];
    	}
    

  • 0
    B

    @hanyu92 Could you please elaborate what you mean by a 01 pack solution? Thanks in advance!


Log in to reply
 

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