Straightforward (yet kinda expensive) solution using queue (Java)


  • 0
    S

    Using queue we can easily compare the target character with what we have on hand without worrying about pointers.
    Here's the solution:

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            if (s.length() == 0 && t.length() == 0) {
                return true;
            }
            if (s == null || t == null || t.length() == 0) {
                return false;
            }
            
            LinkedList<Character> queue = new LinkedList<>();
            for (int i = 0; i < s.length(); ++i) {
                queue.offer(s.charAt(i));
            }
            
            for (int i = 0; i < t.length(); ++i) {
                if (!queue.isEmpty()) {
                    char target = queue.peek();
                    if (t.charAt(i) == target) {
                        queue.poll();
                    } 
                } else {
                    break;
                }
            }
            
            return queue.isEmpty();
        }
    }
    
    • The space complexity is O(s) i.e. the size of the queue
    • The time complexity is O(s + t), putting things in queue ( O(s) ) and traversing through t ( O(t) ).

Log in to reply
 

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