-
Notifications
You must be signed in to change notification settings - Fork 0
/
_20220825.kt
103 lines (83 loc) · 2.71 KB
/
_20220825.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
@file:Suppress("DuplicatedCode", "ClassName", "ObjectPropertyName")
package _2022._08
import Testable
import utils.assertEqualTo
import utils.runTimedTests
// 131. Palindrome Partitioning
// https://leetcode.com/problems/palindrome-partitioning/
private interface LC_131 {
fun partition(s: String): List<List<String>>
// not working
private class M1 : LC_131 {
val res = ArrayList<ArrayList<String>>()
val cur = ArrayList<String>()
override fun partition(s: String): List<List<String>> {
dfs(s, 0, 0)
return res
}
fun dfs(s: String, left: Int, right: Int) {
if (left > right) return
if (right >= s.length) return
if (right == s.length-1) {
if (cur.isNotEmpty()) {
res.add(ArrayList(cur))
cur.clear()
}
}
if (isPalindrome(s, left, right)) cur.add(s.substring(left, right+1))
for (r in right+1 until s.length-1){
dfs(s, left, r)
}
dfs(s, left+1, left+2)
}
fun isPalindrome(s: String, left: Int, right: Int) : Boolean {
if (left < 0 || right >= s.length || left > right) return false
if (left == right) return true
var left = left
var right = right
while(left <= right) {
if (s[left] != s[right]) return false
left--
right++
}
return true
}
}
}
// 17. Letter Combinations of a Phone Number
// https://leetcode.com/problems/letter-combinations-of-a-phone-number/
private interface LC_17 {
fun letterCombinations(digits: String): List<String>
private class M1 : LC_17 {
val map = arrayOf(
charArrayOf(), // 0
charArrayOf(), // 1
"abc".toCharArray(),
"def".toCharArray(),
"ghi".toCharArray(),
"jkl".toCharArray(),
"mno".toCharArray(),
"pqrs".toCharArray(),
"tuv".toCharArray(),
"wxyz".toCharArray()
)
override fun letterCombinations(digits: String): List<String> {
var res = ArrayList<String>()
val list = digits.map { map[it-'0'] }
for (d in list) {
if (res.isEmpty()) {
res.addAll(d.map { it.toString() })
} else {
res.flatMap { s ->
d.map { "$s$it" }
}.also {
res = ArrayList(it)
}
}
}
return res
}
}
}
val _20220825 = listOf<Testable>(
)