LeetCode 844. 백스페이스 문자열 비교
설명:
두 개의 문자열
S
및 T
가 주어지면 둘 다 빈 텍스트 편집기에 입력할 때 동일하면 반환합니다. #은 백스페이스 문자를 의미합니다.빈 텍스트를 백스페이스한 후 텍스트는 계속 비어 있습니다.
예 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
예 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
예 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
예 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
해결책:
시간 복잡도 : O(n)
// In this solution we use an array like a stack
// to create 2 new strings from the inputs
// Then we check if they are equal
const backspaceCompare = (S, T) => buildString(S) === buildString(T);
// Helper function
function buildString(S) {
// Data structure that we will use to create the compare strings
const stack = [];
for (const c of S) {
// Add letter to the stack if it is not '#'
if (c != '#')
stack.push(c);
// Remove the most recently added letter if we encounter '#'
// and the stack is not empty
else if (stack.length!==0) {
stack.pop();
}
}
// Convert array to an string
return stack.join('');
}
Reference
이 문제에 관하여(LeetCode 844. 백스페이스 문자열 비교), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/cod3pineapple/leetcode-844-backspace-string-compare-1ikg텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)