[Easy] LeetCode - no.392 Is Subsequence : Java

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

2개의 String 값인 s와 t가 주어졌을 때, s가 t의 subsequence라면 true를 반환, 아니라면 false를 반환할 것

이 때  subsequence란 t의 순서를 유지하면서, 특정 문자를 지움으로써 s를 만들 수 있는지 여부이다.

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

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

 

 

 

풀이

class Solution {
    public boolean isSubsequence(String s, String t) {
        int count = 0;
        int idx = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            for (int j = idx; j < t.length(); j++) {
                if (t.charAt(j) == c) {
                    idx = j + 1;
                    count++;
                    break;
                }
            }
        }

        if (count == s.length()) {
            return true;
        } else {
            return false;
        }
    }
}

• count와 idx를 각각 0으로 선언
• for문을 순회하며 s.charAt(i)로 char c 설정
• 내부 for문을 순회하며 t.charAt(j)가 c와 같은지 여부 판단
  • 이 때 서로 일치한다면
    • idx = j + 1 → 인덱스 j 이후부터 다시 순회하기 위함
    • count++ (찾아낸 일치하는 경우의 수)
    • break;
• count가 s.length()와 같다면 true, 다르다면 false 반환

 

 

풀이 2

  // 투 포인터
  public static boolean isSubsequence2(String s, String t) {
    int sp = 0;
    int tp = 0;

    while (sp < s.length() && tp < t.length()) {
      if (s.charAt(sp) == t.charAt(tp)) {
        sp++;
      }
      tp++;
    }

    return sp == s.length();
  }

• 2개의 포인터 사용 : sp, tp
• while문 사용 (sp와 tp가 각각의 length()를 넘지 않을 경우)
  • s.charAt(sp)와 t.charAt(tp)가 일치한다면 sp++, tp++
  • s.charAt(sp)와 t.charAt(tp)가 일치하지 않는다면 tp만 ++
• sp가 s.length()와 같다면 전부 찾아낸 것이므로 true, 아니라면 false 반환