[LeetCode] 1047. Remove All Adjacent Duplicates In String / Swift

[문제 보기]

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

 

Example 1:

Input: s = "abbaca" Output: "ca" Explanation: For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy" Output: "ay"

 

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

 

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Remove All Adjacent Duplicates In String - LeetCode

---

풀이 과정

방법1)

입력으로 주어진 문자열을 순서대로 탐색하는 포인터를 이용해서 해결하는 방법이다.

포인터가 가리키는 위치의 글자(str[i])와 그 다음 번째에 있는 글자(str[i+1])가 같은 글자라면 (i...i+1)범위에 있는 영역을 지운다.

여기서 문자열 다시 처음으로 돌아가서 탐색하지 않고, 방금 탐색했던 위치 - 1로 가서 이어서 탐색을 한다.

 

class Solution {
    func removeDuplicates(_ s: String) -> String {
        var str = s.map{String($0)}
        
        var i = 0
        while i < str.count - 1 && str.count > 1 {
            if str[i] == str[i + 1] {
                str.removeSubrange((i...i+1))
                if i > 0 { i -= 1 }
                continue
            }
            
            i += 1
        }
        return str.joined()
    }
}

 

방법2)

스택을 이용하여 푸는 방법이다.

class Solution {
    func removeDuplicates(_ s: String) -> String {
        var stack = [String]()
        var str = s.map{String($0)}
        for element in str {
            if let top = stack.last, top == element {
                stack.removeLast()
            } else {
                stack.append(element)
            }
        }
        
        return stack.reduce(""){$0+$1}
    }
}