DFS로 가능한 조합을 만들며 확인 → 시간 초과
words에 있는 문자가 최초 발견될 경우, 해당 idx를 시작으로 다음 문자를 DFS로 탐색
시간 초과 테스트 케이스
s = “aaaaaaaaaaaaaaaaaaa…” words = [“a”, “a”, “a”, “a”, …]
class Solution {
var s = ""
var interval = 0
val answer = mutableListOf<Int>()
var words = arrayOf<String>()
fun findSubstring(s: String, words: Array<String>): List<Int> {
this.s = s
this.words = words
interval = words[0].length
// 문자열에서 words에 있는 단어의 최초 등장 찾기
for (i in 0..s.length - interval) {
val key = s.substring(i, i + interval)
if (words.contains(key)) {
// 모든 word 체크용 visited
val visited = words.toList().toTypedArray()
visited[visited.indexOf(key)] = ""
dfs(i + interval, visited)
}
}
return answer
}
// 시작 idx를 기준으로 word의 길이만큼만 확인
fun dfs(start: Int, visited: Array<String>) {
if (!visited.any { it != "" }) { // 모든 words 탐색
answer.add(start - (visited.size * interval))
return
}
if (start + interval > s.length) return // s의 범위를 벗어남
// 다음 단어가 word에 속하는지 확인
val sub = s.substring(start, start + interval)
val idx = visited.indexOf(sub)
if (idx != -1) {
visited[idx] = ""
dfs(start + interval, visited)
}
}
}
시간 복잡도: s 순회 X words 순회(visited) X words 순회(visited) …
🚫⁉
- 한번의 탐색에서 word의 길이만큼만 탐색하고, 다시 DFS 탐색을 함
- 매 DFS 탐색마다 words 전체 탐색
Substring이 words를 모두 포함하는지 한번에 확인
words를 “ “으로 구분한 문자열로 만들고 잘라낸 Substring에 있는 단어(word로 길이로 자른)가 있으면 replace해줌
class Solution {
var interval = 0
var words = arrayOf<String>()
fun findSubstring(s: String, words: Array<String>): List<Int> {
this.words = words
val answer = mutableListOf<Int>()
interval = words[0].length
// 문자열에서 words에 있는 단어의 최초 등장 찾기
for (i in 0..s.length - interval) {
val key = s.substring(i, i + interval)
if (words.contains(key) && i + interval * words.size <= s.length) {
if (isContainAll(s.substring(i, i + interval * words.size))) answer.add(i)
}
}
return answer
}
// Substring에 모든 words가 포함되어 있는지 확인
fun isContainAll(str: String): Boolean {
var visited = words.joinToString(" ") // words를 공백으로 구분한 문자열로 변환
for (i in str.indices step interval) {
val sub = str.substring(i, i + interval)
// subString이 word에 없으면 바로 리턴
if (visited.indexOf(sub) == -1) return false
// subString이 word에 있다면 replace로 삭제
visited = visited.replaceFirst(sub, "")
}
return (visited == " ".repeat(words.size-1))
}
}
시간 복잡도: s 순회 X Substring 순회 X words 순회(visited) = n^3
🚫⁉
-
replace도 내부에 Sequence로 처리 되는데 왜 Sol3이랑 속도차이가 나는지 모르겠음
(빈번한 String 객체 갱신?)
visited를 배열로 처리
Substring을 word길이로 짤라서 배열로 만듬
words의 문자를 위의 배열에서 있는지 확인
class Solution {
var interval = 0
var words = arrayOf<String>()
fun findSubstring(s: String, words: Array<String>): List<Int> {
this.words = words
val answer = mutableListOf<Int>()
interval = words[0].length
// 문자열에서 words에 있는 단어의 최초 등장 찾기
for (i in 0..s.length - interval) {
val key = s.substring(i, i + interval)
if (words.contains(key) && i + interval * words.size <= s.length) {
if (isContainAll(s.substring(i, i + interval * words.size))) answer.add(i)
}
}
return answer
}
fun isContainAll(str: String): Boolean {
// word 길이로 나누어 Substring 배열로 변환
val checkList = str.chunked(interval).toTypedArray()
for (word in words) {
// word가 subString에 없으면 바로 리턴
val idx = checkList.indexOf(word)
if (idx == -1) return false
// word가 subString에 있으면 바로 값 삭제
checkList[idx] = ""
}
return !(checkList.any { it != "" })
}
}
시간 복잡도: s 순회 X words 순회(visited) X Substring 순회 = n^3
