[Swift] [78일차] 1408_LEETCODE

1408. String Matching in an Array

---

문제 설명

1. 단어가 여러개 주어진다. [String]
2. 단어들 중에서 포함관계에 있는 단어들을 따로 모아서 return

---

문제 풀이

1. 모든 단어에 포함된 문자열이여야하는지 헷갈렸는데, 그렇지 않고, 한개라도 속한게 있으면 리턴값에 포함시켜주면 되는 것이었다.
2. 어떻게 포함관계를 점검할까?에서contains메소드를 사용해주기로 했다.

var a = "mass" ; var b = "as"
print(a.contains(b)) // true

3. 다만 반대로 b.contains(a)는 false가 나오기 때문에 양쪽을 다 판단해줘야했다.

class Solution {
    func stringMatching(_ words: [String]) -> [String] {
        var answer = [String]()
        for i in 0 ..< words.count - 1 {
            let current_word = words[i]
            for j in i + 1 ..< words.count {
                if words[i].contains(words[j]) {
                    answer.append(words[j])
                }
                else if words[j].contains(words[i]) {
                    answer.append(words[i])
                }
            }
        }

        return answer
    }
}

잘 푼것 같았는데, 제출 과정에서 다음과 같이 에러가 떴다.

이게 od가 두 단어에 포함되어있다보니 이렇게 오류가 발생했다.

answer의 타입을 SET으로 변경해서 알아서 이게 걸러질 수 있게 수정했다.

최종 제출 코드

class Solution {
    func stringMatching(_ words: [String]) -> [String] {
        var answer = Set<String>()
        for i in 0 ..< words.count - 1 {
            for j in i + 1 ..< words.count {
                if words[i].contains(words[j]) {
                    answer.insert(words[j])
                }
                else if words[j].contains(words[i]) {
                    answer.insert(words[i])
                }
            }
        }

        return Array(answer)
    }
}

---

타인의 코드

class Solution {
    func stringMatching(_ words: [String]) -> [String] {
        let words = words.sorted { $0.count < $1.count }
        var res = [String]()
        for (i, word) in words.enumerated() {
            print(word)
            var j = i + 1
            while j < words.count {
                if words[j].contains(word) {
                    res.append(word)
                    break
                }
                j += 1
            }
        }
        return res
    }
}

내가 위에서 언급했던 3번 <다만 반대로 b.contains(a)는 false가 나오기 때문에 양쪽을 다 판단해줘야했다.> 이 문제를 해결해주기 위해 여기서는 미리 길이로 sorting을 한 뒤에 수행해준걸 볼 수 있다. 그리고, 그렇게 하니까 발견하자마자 내무 for문에서 탈출해주면 이제 빠른 코드가 완성된다.

코드 수정안

위에서 본대로 sorting 후, 내부 for문의 break를 수행할 수 있도록해서 바견하면 바로 다음 타겟을 보도록 했다.

class Solution {
    func stringMatching(_ words: [String]) -> [String] {
        var answer = Set<String>()
        var words = words.sorted {$0.count < $1.count}
        for i in 0 ..< words.count - 1 {
            for j in i + 1 ..< words.count {
                if words[i].contains(words[j]) {
                    answer.insert(words[j])
                    break
                }
                else if words[j].contains(words[i]) {
                    answer.insert(words[i])
                    break
                    
                }
            }
        }

        return Array(answer)
    }
}

33ms -> 23ms 로 개선