Backspace String Compare using R | Fresco Play

Author: neptune | 05th-Nov-2023

Problem Description: The problem asks us to determine whether two strings, `s1` and `s2`, are equal after applying backspace operations. Backspacing removes the previous character in the string, and we need to compare the final strings formed after backspacing.


Approach and Algorithm

To solve the problem, we can use a stack data structure to simulate the backspacing operation. The algorithm can be summarised as follows:


1. Initialize two empty stacks, `stack1` and `stack2`, to store the characters of `s1` and `s2` after backspacing.

2. Iterate through each character, `ch`, in `s1`:

   - If `ch` is not '#', push it onto `stack1`.

   - If `ch` is '#', check if `stack1` is not empty. If it is not empty, pop the top element from `stack1` (backspace operation).

3. Iterate through each character, `ch`, in `s2`, and apply the same steps as in step 2 for `stack2`.

4. After iterating through both strings, compare the contents of `stack1` and `stack2`. If they are equal, return 1. Otherwise, return 0.


Pseudocode

Here's the pseudocode for the algorithm:


compareStrings(s1, s2):

    stack1 = empty stack

    stack2 = empty stack


    # Iterate through s1

    for ch in s1:

        if ch != '#':

            push ch onto stack1

        else:

            if stack1 is not empty:

                pop the top element from stack1


    # Iterate through s2

    for ch in s2:

        if ch != '#':

            push ch onto stack2

        else:

            if stack2 is not empty:

                pop the top element from stack2


    # Compare the stacks

    if stack1 is equal to stack2:

        return 1

    else:

        return 0



Implementation in R


compareStrings <- function(s1, s2) {

    stack1 <- list()

    stack2 <- list()


    # Iterate through s1

    for (ch in strsplit(s1, "")[[1]]) {

        if (ch != "#") {

            stack1 <- c(stack1, ch)

        } else {

            if (length(stack1) > 0) {

                stack1 <- stack1[-length(stack1)]

            }

        }

    }


    # Iterate through s2

    for (ch in strsplit(s2, "")[[1]]) {

        if (ch != "#") {

            stack2 <- c(stack2, ch)

        } else {

            if (length(stack2) > 0) {

                stack2 <- stack2[-length(stack2)]

            }

        }

    }


    # Compare the stacks

    if (identical(stack1, stack2)) {

        return(1)

    } else {

        return(0)

    }

}



Implementation in Python


def compareStrings(s1, s2):

    stack1 = []

    stack2 = []


    # Iterate through s1

    for ch in s1:

        if ch != '#':

            stack1.append(ch)

        else:

            if stack1:

                stack1.pop()


    # Iterate through s2

    for ch in s2:

        if ch != '#':

            stack2.append(ch)

        else:

            if stack2:

                stack2.pop()


    # Compare the stacks

    if stack1 == stack2:

        return 1

    else:

        return 0



Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the longer string between `s1` and `s2`. This is because we iterate through both strings once. The space complexity is also O(n) since the worst-case scenario is when no backspaces occur, and we need to store all the characters in the stacks.

Testing

You can test the function with the provided sample inputs test cases to validate its correctness.



# Sample test cases

s1 <- "axx#bb#c"

s2 <- "axbd#c#c"

output <- compareStrings(s1, s2)

print(output)  # Output: 1


s1 <- "yf#c#"

s2 <- "yy#k#pp##"

output <- compareStrings(s1, s2)

print(output)  # Output: 1


s1 <- "hacc#kk#"

s2 <- "hb##ackk##"

output <- compareStrings(s1, s2)

print(output)  # Output: 0



The function should produce the expected output for each test case, demonstrating the correctness of the solution.

Conclusion

In this article, we discussed how to solve the "Backspace String Compare" problem using R. By simulating the backspacing operation using stacks, we can compare the final strings formed after applying backspaces. The provided algorithm and implementation offer an efficient solution to the problem.




👉 Read More
The Blunder | Hackerrank
5. Solution of Hacker Rank Weather Observation Station 8.
7.Solution of Hacker Rank The Report
Identifying the Odd One Out in a Series of Strings | Hackerrank
4. Solution of Hacker Rank Weather Observation Station 6.
3. Solution of Hacker Rank Weather Observation Station 4.
The PADS | Hackerrank
6. Solution of Hacker Rank Employee Salaries.
1. Basic SQL Select Query of Hacker Rank.
Generate Fibonacci Sequence - JavaScript | Hackerank
Team Formation Hackerrank | Julia
Modified 0-1 knapsack problem | Frsco Play Hackerrank
2. Solution of Hacker Rank Weather Observation Station 3.
Weather Observation Station 18 | Hackerrank
Solving the Ice Cream Parlor Problem | Hackerrank
AngularJS - Know Tech Frameworks | Fresco Play
PySpark Milestone Black Friday Sales Data | Fresco Play Hackerrank
Top Earners | HackerRank
Git - Recovering Discarded Changes
Python - Number Based Problem | Hackerrank
Explore more Blogs...