[알고리즘문제] 릿코드 Is Subsequence

https://leetcode.com/problems/is-subsequence/

Is Subsequence - LeetCode

문자열s, 문자열t를 준다.

 

문자열t에서 문자열s가 포함되어 있다면 true, 포함되어 있지 않다면 false

여기서 포함되어 있다는 의미는 문자열 s의 문자가 문자열 t의 문자에 순서대로 배치되어 있다는 의미이다.

ex) s가 "abc", t가 "ahbgdc"일 경우 t의 0번째, 2번째, 5번째에 각각 배치되어 있으므로 true이다

ex) s가 "abc", t가 "bdcha"일 경우 t의 4번째, 0번째, 2번째 이런 형태로 배치되어 있으므로 false를 반환 한다.

impl Solution {
    pub fn is_subsequence(s: String, t: String) -> bool {
        if s.len() == t.len() && s != t { return false; }
        let text : Vec<char> = t.chars().collect();
        let mut next: usize = 0;
        for c in s.chars(){
            let mut next_step : bool = false;
            for i in next..text.len(){
                if text[i] == c{
                    next = i + 1;
                    next_step = true;
                    break;
                }
            }
            if next_step == false {
                return false;
            }
        }
        true
    }
}

s의 문자를 순회하며 t에서 찾았을 경우 찾은 index+1을 저장한 후 다시 t를 index+1번째 부터 순회하여 모두 찾은 경우 true, 찾지 못한 경우 false를 반환한다.

 

time complexity : O(nm)

space complexity : O(nm)