Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. String

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.

Solutions

The key idea is to process the strings as if they were being typed into a text editor, where the backspace character removes the previous character.

Approach – Brute Force Technique

This algorithm compares two strings after processing backspaces in them. It uses two stacks to simulate the typing and backspacing process. For each character in the strings, if it's a backspace and the stack is not empty, the top character is removed. If it's not a backspace, the character is added to the stack. After processing both strings, it compares the resulting stacks. If they are equal, it returns true; otherwise, it returns false.

Steps

  1. Check for null or empty strings: If either s or t is null or empty, the method returns true. If s is null or empty, it returns false. If t is null or empty, it also returns false.

  2. Initialize variables: A character variable backspace is initialized with the value '#'. Two stacks sStack and tStack are created to hold the characters of s and t respectively.

  3. Process string s: For each character in s, if the character is a backspace and sStack is not empty, the top character is popped from sStack. If the character is not a backspace, it is pushed onto sStack.

  4. Process string t: The same process is repeated for t, but with tStack.

  5. Compare stack sizes: If the sizes of sStack and tStack are not equal, the method returns false because the processed strings are of different lengths.

  6. Compare stacks: For each item in sStack, the method pops an item from tStack and compares the two. If they are not equal, the method returns false.

  7. Return true: If all the above checks pass, the method returns true, indicating that the processed strings s and t are equal.

public class Solution
{
    public bool BackspaceCompare(string s, string t)
    {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))
        {
            return true;
        }
        if (string.IsNullOrEmpty(s))
        {
            return false;
        }
        if (string.IsNullOrEmpty(t))
        {
            return false;
        }
        char backspace = '#';
        Stack<char> sStack = new();
        Stack<char> tStack = new();

        foreach (var item in s)
        {
            if (item == backspace && sStack.Count > 0)
            {
                sStack.Pop();
            }

            if (item != backspace)
            {
                sStack.Push(item);
            }
        }

        foreach (var item in t)
        {
            if (item == backspace && tStack.Count > 0)
            {
                tStack.Pop();
            }

            if (item != backspace)
            {
                tStack.Push(item);
            }
        }

        if (sStack.Count != tStack.Count)
        {
            return false;
        }

        foreach (var item in sStack)
        {
            var second = tStack.Pop();

            if (item != second)
            {
                return false;
            }
        }

        return true;
    }
  
}

Complexity

  • Time complexity: O(S+T)

  • Space complexity: O(S+T)

Approach – Two Pointers Technique

Uses two pointers, one for each string, starting from the end and moving backwards. When a pointer encounters a backspace character, it moves back until it finds a non-backspace character. The algorithm then compares these characters. If they're not the same, it returns false. If all compared characters are the same, it returns true.

Steps

  1. Initialize two pointers: Start with two pointers, one at the end of each string.

  2. Iterate over the strings: Move the pointers backwards through the strings. If a pointer encounters a backspace character, it keeps moving backwards until it finds a non-backspace character. This simulates the effect of the backspace.

  3. Compare characters: Once both pointers are pointing to non-backspace characters, compare these characters. If they're not the same, return false.

  4. Repeat until pointers meet the start of the strings: Repeat steps 2 and 3 until both pointers have reached the start of their respective strings.

  5. Return true: If all compared characters were the same, return true.

public class Solution
{
   public bool BackspaceCompare(string s, string t)
   {
       int i = s.Length - 1, j = t.Length - 1;
       int skipS = 0, skipT = 0;

       while (i >= 0 || j >= 0)
       {
            // While there are characters to compare
           while (i >= 0)
           { // Find position of next possible char in s
               if (s[i] == '#') { skipS++; i--; }
               else if (skipS > 0) { skipS--; i--; }
               else break;
           }
           while (j >= 0)
           { 
               // Find position of next possible char in t
               if (t[j] == '#') { skipT++; j--; }
               else if (skipT > 0) { skipT--; j--; }
               else break;
           }
           // If two actual characters are different
           if (i >= 0 && j >= 0 && s[i] != t[j])
               return false;
           // If expecting to compare char vs nothing
           if ((i >= 0) != (j >= 0))
               return false;
           i--; j--;
       }
       return true;
   }


}

Complexity

  • Time complexity: O(S+T)

  • Space complexity: O(1)

PreviousValid Palindrome IINextFirst Unique Character in a String

Last updated 1 year ago