[JAVA] 392. Is Subsequence

목차

문제

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

 

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

 

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 104
• s and t consist only of lowercase English letters.

 

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

아이디어

Follow up대로면, 하나씩 다 확인해야한다. 이때 이중포문을 돌린다던가... 그런 바보같은 짓이 아닌, DP의 관점에서 생각해보도록 하자.

 

s와 t 두 단어 글자마다 포인터를 두고, 한글자씩 체크해나가며 포인터 각각의 글자가 일치하면 두 포인터 다 한칸 이동하고, 그렇지 않은 경우, t 포인터만 이동하도록 한다.

 

최종적으로, s 포인터가 마지막 글자를 이탈했을 경우, 모두 찾았다는 뜻이므로 true를 리턴하고, 그렇지 않을 경우 false를 리턴하자.

풀이

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

다른 풀이

class Solution {
    public boolean isSubsequence(String s, String t) {
        
        int idxS = 0;
        
        //for문 안에서 이런식으로 코드를 넣어둔건 가독성 측면에서 좋아보이진 않는다...
        for(int idxT = 0; idxT<t.length() && idxS<s.length(); idxT++{
        	if(t.charAt(i) == s.charAt(idx)){
            	idxS++;
            }
        }
        
        return idxS == s.length();
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        return isSubsequence(s, t, s.length() - 1 , t.length() - 1;);
    }

    private boolean isSubsequence(String s, String t, int m, int n){
		// BASE CASE[ IF WE HAVE COMPLETED OUR S STRING THEN WE HAVE A SUBSEQUENCE ELSE NO]
        // String s와 t의 단어를 거꾸로 탐색하는 코드.
        // 굉장히... 별로 마음에 안듬..!
        if(m < 0) {
        	return true;
        }
        
        if(n < 0) {
        	return false;
        }
        
        if(s.charAt(m) == t.charAt(n)){
        	return isSubsequence(s, t, m - 1, n - 1);
        }
        
        return isSubsequence(s, t, m, n - 1);
    }
}