LeetCode 844. 백스페이스 문자열 비교

설명:



두 개의 문자열 ST 가 주어지면 둘 다 빈 텍스트 편집기에 입력할 때 동일하면 반환합니다. #은 백스페이스 문자를 의미합니다.

빈 텍스트를 백스페이스한 후 텍스트는 계속 비어 있습니다.

예 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('');
}

좋은 웹페이지 즐겨찾기