1408. String Matching in an Array | 배열의 문자열 일치

https://leetcode.com/problems/string-matching-in-an-array/description/

 

이 문제는 Input으로 여러 개의 문자열로 이루어진 리스트 타입 words를 입력받는데

예제는 아래와 같다.

예제 1.
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
해설 : "as"가 "mass"에 포함되고 "hero"가 "superhero"에 속하기 때문에 답은 ["as","hero"]가 된다

예제 2.
Input: words = ["leetcode","et","code"]
Output: ["et","code"]
해설: "et", "code" 는 "leetcode"에 속한다.

예제 3.
Input: words = ["blue","green","bu"]
Output: []
해설 : 서로 포함되는 글자가 없기 때문에 답이 없다. 

 

이 문제를 보고 저번에 풀었던 RansomNote 문제에서 내가 처음에 작성했던 코드가 생각났다.

이번에는 반드시 맞을 것이라 생각하고 열심히 코드를 짠 결과

class Solution {
    public List<String> stringMatching(String[] words){
    	// 중복 제거용 set
        Set<String> set = new HashSet<>();
        int len = 0;
		
        // words 문자열을 하나씩 꺼냄
        for(String temp : words){
            len = temp.length();
            // 비교용 문자열을 꺼냄
            for(String temp2 : words){
            	// 만약 문자열이 같지않고, 문자열의 길이가 비교용 문자열보다 길다면
                if(!temp.equals(temp2) && len < temp2.length()){
                    for(int i = 0; i < temp2.length(); i++){
                    	// 문자열의 길이가 초과되지 않을때 까지 잘라서 비교한다.
                        if(len+i <= temp2.length()){
                            if(temp2.substring(i,len+i).equals(temp)){
                                set.add(temp);
                            }
                        }
                    }
                }
            }
        }
        // 결과를 다시 List<String> 타입으로 변환한다.
        List<String> result = new ArrayList<>(set);

        return result;
    }
}

 

이렇게 지저분한 코드가 완성됐다.

 

제출결과 맞긴 했는데 메모리를 45.1MB나 먹고 시간도 12ms나 걸렸다.

평균적으로 꼴찌였기에 새롭게 다시 짜기로 했다.

 

그러다가 Java에 문자열이 포함되어 있는 여부를 확인할 수 있는 함수인 .contains( )가 있다는 것을 알았고,

그 함수를 사용해서 다시 작성하였다.

class Solution {
    public List<String> stringMatching(String[] words){
    	// 중복 제거용 set
        Set<String> set = new HashSet<>();
        
        for(int i = 0; i < words.length;i++){
            for(int j = i+1; j < words.length; j++){
            	// 해당 문자열에 포함된다면...
                if(words[i].contains(words[j])){
                    set.add(words[j]);
                }else if(words[j].contains(words[i])){
                    set.add(words[i]);
                }
            }
        }
		// List<String>타입으로 변환
        List<String> result = new ArrayList<>(set);

        return result;
    }
}

여기서 if문이 있는데 한 번 더 비교한 이유는 그냥 if(words [i]. contains(words [j])) 만 작성하면

관련된 모든 값이 다 나와서 한 번 더 반대로 검증해야 했다.

 

코드는 여전히 지저분하지만 결과는 확실히 좋았다.

실행 시간은 5ms가 되었고 메모리는 42.6MB가 되었다.

 

그래도 아직 평균에 못 미치는데 그건 다음에 다시 봐야겠다.