Study Notes
  • Kuma Blog
  • AI
    • AI-Resources
    • AI-books
    • AI_Blogs
      • AI---test
      • AI-test
      • The-Future-of-AI---test
      • The-Future-of-AI-in-2025-Predictions-and-Insights
      • The-Future-of-AI-in-2025-Predictions-and-Insights
      • The-Future-of-AI-in-2025-Predictions-and-Insights_2025-05-24
      • The-Future-of-AI-in-2025-Predictions-test
      • kuma-test-1
      • kuma-test
      • test
    • Prompts
      • Prompts Free Courses
  • Movies
    • 2024
    • 2024
    • 2024
  • Google
    • chunked-palindrome
  • Setup
    • How to add a new user into Ubuntu and setup ssh key?
    • How to set up VSCode remote server connect with browser with Docker
  • kubernetes
  • Books
    • Designing-Data-Intensive-Applications
      • 第一章 — 可靠性,可扩展性,可维护性的应用程序(Reliable, Scalable, and Maintainable Applications)
    • System-Performance
      • Design-Data-Intensive-Application
      • Chapter 2: Methodologies
  • Languages
    • japanese
      • japanese-week
  • Leetcode
    • 30DayChallenge
      • LRU-cache
      • backspace-string-compare
      • binary-tree-maximum-path-sum
      • bitwise-and-number-range
      • check-string-valid-sequence-from-root-to-leaves-path-in-bst
      • construct-binary-search-tree-from-preorder-traversal
      • contiguous-array
      • counting-elements
      • diameter-of-binary-tree
      • first-unique-number
      • group-anagrams
      • jump-game
      • last-stone-weight
      • leftmost-column-with-at-least-a-one
      • longest-common-subsequect
      • maximal-square
      • maximum-subarray
      • middle-of-the-linked-list
      • min-stack
      • minimun-path-sum
      • move-zeroes
      • perform-string-shifts
      • product-of-array-except-itself
      • search-in-rotated-sorted-array
      • subarray-sum-equals-k
      • valid-parenthesis-string
    • English Solution
      • 1168.optimize-water-distribution-in-a-village-en
      • 1171.remove-zero-sum-consecutive-nodes-from-linked-list-en
      • 1177.can-make-palindrome-from-substring-en
      • 1343.number-of-avg-subarr-sizek-greater-or-equal-threshold
      • 1345.jump-game-iv
      • 25.reverse-nodes-in-k-groups-en
      • 474.ones-and-zeros-en
      • 53.maximum-sum-subarray-en
      • 547.friend-circles-en
      • 79.word-search-en
    • May2020Challenge
      • check-if-straight-line
      • cousins-in-binary-tree
      • find-town-judge
      • first-bad-version
      • first-unique-character-in-a-string
      • flood-fill
      • implement-trie
      • jewels-and-stones
      • majority-element
      • maximum-sum-circular-subarray
      • number-complement
      • odd-even-linkedlist
      • ransom-note
      • remove-k-digits
      • single-element-in-sorted-array
      • valid-perfect-square
    • python
      • 000017-Letter-Combinations-of-a-Phone-Number
      • 000032-Longest-Valid-Parentheses
      • 000033-Search-in-Rotated-Sorted-Array
      • 000046-Permutations
      • 000074-Search-a-2D-Matrix
      • 000077-Combinations
      • 000081-Search-in-Rotated-Sorted-Array-II
      • 000137-single-number-ii
      • 000139-Word-Break
      • 000207-courses-schedule
      • 000209-Minimum-Size-Subarray-Sum
      • 000376-wiggle-subsequence
      • 000445-Add-Two-Numbers-II
      • 000486-Predict-the-Winner
      • 000518-Coin-Change-II
      • 000673-Number-of-Longest-Increasing-Subsequence
      • 000688-Knight-Probability-in-Chessboard
      • 000735-Asteroid-Collision
      • 000852-Peak-Index-in-a-Mountain-Array
      • 859-Buddy-Strings
      • 000864-Shortest-Path-to-Get-All-Keys
      • 000920-Number-of-Music-Playlists
      • 001218-Longest-Arithmetic-Subsequence-of-Given-Difference
      • 001235-Maximum-Profit-in-Job-Scheduling
      • 001493-Longest-Subarray-of 1-After-Deleting-One-Element
      • Problem
      • 002024-Maximize-the-Confusion-of-an-Exam
      • 2305-Fair-Distribution-of-Cookies
      • 002616-Minimize-the-Maximum-Difference-of-Pairs
      • 00802-Find-Eventual-Safe-States
    • 中文版解题
      • 1147.longest-chunked-palindrome-decomposition-cn
      • 1168.optimize-water-distribution-in-a-village-cn
      • 1171.remove-zero-sum-consecutive-nodes-from-linked-list-cn
      • 1177.can-make-palindrome-from-substring-cn
      • 215.kth-largest-element-in-an-array-cn
      • 25.reverse-nodes-in-k-groups-cn
      • 30.substring-with-concatenation-of-all-words-cn
      • 4.median-of-two-sorted-array-cn
      • 460.LFU-cache-cn
      • 474.ones-and-zeros-cn
      • 53.maximum-sum-subarray-cn
      • 79.word-search-cn
  • Readings
    • 2020
      • Design-Data-Intensive-Application
      • 亲爱的提奥
      • 理想国
      • 贫穷的本质
Powered by GitBook
On this page
  • Problem
  • Problem Description
  • Solution 1
  • Complexity Analysis
  • Code
  • Solution 2 (follow up)
  • Complexity Analysis

Was this helpful?

  1. Leetcode
  2. 30DayChallenge

backspace-string-compare

PreviousLRU-cacheNextbinary-tree-maximum-path-sum

Last updated 5 years ago

Was this helpful?

Problem

Problem Description

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

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 = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:

1 <= S.length <= 200
1 <= 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?

Solution 1

In this solution, we build a new string after backspace.

  • From left to right, if curr char != '#', append to newString.

  • If curr char == '#', check newString is null?

    • if newString is null, do nothing, continue

    • if newString is not null, delete last char.

  • return newString.

  • Compare new build string from S and T.

For example:

Complexity Analysis

Time Complexity: O(N + M)

Space Complexity: O(N + M)

  • N - length of String S

  • M - length of String T

Code

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return buildStr(S).equals(buildStr(T)); 
    }

    private String buildStr(String s) {
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        int len = s.length();
        while (idx < len) {
            char curr = s.charAt(idx);
            if (curr != '#') {
                sb.append(curr);
            } else if (sb.length() > 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
            idx++;
        }
        return sb.toString();
    } 
}

Solution 2 (follow up)

This solution is to compare char on the fly.

  • Scan both String S and T from right to left

  • Define '#' count and index: sIdx, tIdx, if encounter '#', count++, else count--.

  • Until count = 0, and curr char != '#', check current position char

    • if out of string(S/T) index, then s = *, t = *

    • else s = S.charAt(sIdx), t = T.charAt(tIdx)

  • compare current s == t?

    • if s != t, return false

    • else continue

  • If complete loop S and T, return true.

for example:

Complexity Analysis

Time Complexity: O(N + M)

Space Complexity: O(1)

  • N - length of String S

  • M - length of String T

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int sIdx = S.length() - 1;
        int tIdx = T.length() - 1;
        int sCount = 0;
        int tCount = 0;
        while (sIdx >= 0 || tIdx >= 0) {
            // scan S until count == 0 and current char != '#'
            while (sIdx >= 0 && (sCount > 0 || S.charAt(sIdx) == '#')) {
                sCount += S.charAt(sIdx) == '#' ? 1 : -1;
                sIdx--;
            }
            // get current S index char
            char s = sIdx < 0 ? '*' : S.charAt(sIdx);
            // scan T until count == 0 and current char != '#'
            while (tIdx >= 0 && (tCount > 0 || T.charAt(tIdx) == '#')) {
                tCount += T.charAt(tIdx) == '#' ? 1 : -1;
                tIdx--;
            }
            // get current T index char
            char t = tIdx < 0 ? '*' : T.charAt(tIdx);
            if (s != t) return false;
            sIdx--;
            tIdx--;
        }
        return true;
    }
}
Backspace String Compare
backspace string compare
backspace string compare follow up