LeetCode 솔루션

[5/1] 844. Backspace String Compare

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.01 18:21

7,465 조회
4 댓글
0 추천
0 비추천
목록 게시글 쓰기

[LeetCode 시즌 3] 2022년 5월 1일 문제입니다.

https://leetcode.com/problems/backspace-string-compare/

[Easy] 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.

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.

Follow up: Can you solve it in O(n) time and O(1) space?

#LeetCode, #IBM, #Booking.com, #Apple, #Visa, #Google, #Bloomberg, #tiktok, #Two Pointers, #String, #Stack, #Simulation

링크

https://leetcode.com/problems/backspace-string-compare/ 1092 회 연결

익명
작성일 2022.05.02 11:32

Runtime: 31 ms
Memory Usage: 13.9 MB

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s1, s2 = [], []
        for l in s:
            if l != '#':
                s1.append(l)
            elif len(s1) > 0:
                s1.pop()
        for l in t:
            if l != '#':
                s2.append(l)
            elif len(s2) > 0:
                s2.pop()
        if s1 == s2:
            return True
        else:
            return False

익명
작성일 2022.05.02 17:28

Runtime: 79 ms
Memory Usage: 42.4 MB

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    if (JSON.stringify(backspace(s)) === JSON.stringify(backspace(t))) {
        return true
    } else {
        return false
    }
};

function backspace(s) {
  sArray = s.split('')
  
  while(sArray.includes("#")) {
      //if there are # at beginning, then remove
    while (sArray.indexOf("#") === 0) {
      sArray = sArray.slice(1)
    }
    for (i = 0; i < sArray.length; i++) {
      if (sArray[i] === "#" && sArray.indexOf("#") !== 0) {
        sArray.splice(i-1,2)
        break
      }
    }
  }
  return sArray
}

익명
작성일 2022.05.02 19:10

C++
Runtime: 4 ms, faster than 29.77% of C++ online submissions for Backspace String Compare.
Memory Usage: 6.1 MB, less than 88.27% of C++ online submissions for Backspace String Compare.

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string a, b;
        
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '#' && !a.empty()) {
                a.pop_back();
            }
            else if (s[i] != '#') {
                a += s[i];
            }
        }
        for (int i = 0; i < t.size(); ++i) {
            if (t[i] == '#' && !b.empty()) {
                b.pop_back();
            }
            else if (t[i] != '#') {
                b += t[i];
            }
        }
        return a == b;
    }
};

익명
작성일 2022.05.03 00:31

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Backspace String Compare.
Memory Usage: 6.3 MB, less than 68.20% of C++ online submissions for Backspace String Compare.

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        auto proc = [](string &s) {
            string rs;
            for(auto c: s) {
                if (c != '#') rs.push_back(c);
                if (c == '#' && !rs.empty()) rs.pop_back();
            }
            return rs;
        };
        return proc(s) == proc(t);
    }
};