[LeetCode][Kotlin] 844. Backspace String Compare

844. Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

 

Note that after backspacing an empty text, the text will continue empty.

두 개의 문자열 s와 t가 주어졌을 때, 둘 다 빈 텍스트 편집기에 입력했을 때 같으면 true를 반환합니다. '#'은 백스페이스 문자를 의미합니다. 

빈 텍스트를 백스페이스한 후에는 텍스트가 계속 비어 있게 됩니다.

 

Example 1:

Input: s = "ab#c", t = "ad#c"

Output: true

Explanation: Both s and t become "ac".

 

Example 2:

Input: s = "ab##", t = "c#d#"

Output: true

Explanation: Both s and t become "".

 

Example 3:

Input: s = "a#c", t = "b"

Output: false

Explanation: s becomes "c" while t becomes "b".

 

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

---

코드 1

class Solution {
    fun backspaceCompare(s: String, t: String): Boolean {
        val ls = mutableListOf<Char>()
        val lt = mutableListOf<Char>()

        for (i in s.indices) {
            if (s[i] == '#') {
                if (ls.isNotEmpty()) ls.removeLast()
            } else {
                ls.add(s[i])
            }
        }

        for (i in t.indices) {
            if (t[i] == '#') {
                if (lt.isNotEmpty()) lt.removeLast()
            } else {
                lt.add(t[i])
            }
        }

        return ls == lt
    }
}

 

코드 2

• nextValidChar 함수 = 백스페이스를 한 후의 인덱스 값 (유효한 문자가 없다면 -1 을 반환)
• backspace = 수행해야할 백스페이스 횟수 → 현재 인덱스의 위치한 문자가 '#' 인 경우, '#' 이 아닌 경우

class Solution {
    fun backspaceCompare(s: String, t: String): Boolean {
        fun nextValidChar(str: String, index: Int): Int {
            var backspace = 0
            var i = index

            while (i >= 0) {
                if (backspace == 0 && str[i] != '#') {
                    break
                } else if (str[i] == '#') {
                    backspace++
                } else {
                    backspace--
                }
                i--
            }
            return i
        }

        var indexS = s.length - 1
        var indexT = t.length - 1

        while (indexS >= 0 || indexT >= 0) {
            indexS = nextValidChar(s, indexS)
            indexT = nextValidChar(t, indexT)

            val charS = if (indexS >= 0) s[indexS] else ""
            val charT = if (indexT >= 0) t[indexT] else ""

            if (charS != charT) {
                return false
            }
            indexS--
            indexT--
        }

        return true
    }
}