792. Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/

Number of Matching Subsequences - LeetCode

 

1. 문제와 예제, 그리고 제약사항

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

 

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

 

 

2. 문제 풀이

 

이 문제는 배열, words에 있는 각각의 문자열이 문자열 S의 subsequence인지를 확인하는 문제이다.

 

이 문제에서 가장 중요한 점은 words  배열에 동일한 문자가 반복될 수 있다는 점이다. 

 

예를 들어 words에 총 5개의 문자열이 존재하는데 모두 동일하게 "gg", "gg", "gg", "gg", "gg"인 경우가 있다. 이런 경우에는 5번 모두 체크할 필요 없이 단 한번만 체크를 하면 시간을 줄일 수 있게 된다.

 

이를 위해 Map을 이용하여 각각의 단어를 key로, value에는 중복되는 키의  수를 입력해주면 된다.

위와 같은 경우에는 ("gg", 5)으로 하여 체크를 하면 된다.

 

먼저 가장 많은 추천을 받은 풀이는 다음과 같다.

//JAVA || Easy Solution || 97% faster code


class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        
        Map<String,Integer> map = new HashMap<>();
        for(String str:words){
            map.put(str,map.getOrDefault(str,0)+1);
        }
        
        int ans = 0;
        char ch[] = s.toCharArray();
        
        for(String str:map.keySet()){
            char temp[] = str.toCharArray();
            int i = 0;
            int j = 0;
            
            while(i<ch.length && j<temp.length){
                if(ch[i]==temp[j]){
                    i++;
                    j++;
                }else{
                    i++;
                }
            }
            if(j==temp.length){
                ans+=map.get(str);
            }   
        }       
      return ans;  
    }
}

 

아래는 내가 풀이한 결과이다. 위와 비교하면 상당히 소스가 지저분하다..

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int answer = 0;
        HashMap<String, Integer> map = new HashMap<>();
        
        for(String str : words){
            map.put(str, map.getOrDefault(str, 0) +1);
        }
        char [] target = s.toCharArray();
        
        for(String str : map.keySet()){
            int idx = 0;
            boolean isTrue = true;
            for(char c : str.toCharArray()){
                if(target.length<=idx){
                    isTrue = false;
                    break;
                }
                
                while(target.length>idx){
                    if(c == target[idx++]){
                        isTrue = true;
                        break;
                    }else{
                        isTrue = false;
                    }
                }
            }
            if(isTrue){
                answer = answer + map.get(str);
            }
        }
        return answer;
    }
}