AlgoDaily - Dollar Sign Deletion

Dollar Sign Deletion (Medium)

Good afternoon! Here's our prompt for today.

You may see this problem at Palantir, Lyft, Goldman Sachs, Flatiron Health, Confluent, Asana, Pipedrive, Grammarly, Illumio, and Zoom.

You're given an array of strings containing alphabetical characters and certain $ characters. A $ represents a DELETE action whereby the character before it is deleted.

Each of these strings will be run through a method to operate on the $ DELETE action. We want to find out if the final string is the same for all of them. Let's take an example:

1input = ["f$st", "st"]
2is_dollar_delete_equal(input)
3# True
4# True because both become 'st'

Can you find a solution in O(n) time and constant space?

Constraints

The input arrays can be of any size
Every string has at least a single character
The string will consist of dollar signs and lowercase alphabets
Expected overall time complexity : O(n)
Expected space complexity : O(n) for good solution, O(1) for asymptotically optimal solution

xxxxxxxxxx
​
 
def is_dollar_delete_equal(arr):
    # fill in
    return arr
​
​
import unittest
​
​
class Test(unittest.TestCase):
    def test_1(self):
        assert is_dollar_delete_equal(["f$ec", "ec"]) == True
        print("PASSED: `['f$ec', 'ec']` should return `true`")
​
    def test_2(self):
        assert is_dollar_delete_equal(["a90$n$c$se", "a90n$cse"]) == False
        print("PASSED: `['a90$n$c$se', 'a90n$cse']` should return `false`")
​
    def test_3(self):
        assert is_dollar_delete_equal(["ab$$", "c$d$"]) == True
        print("PASSED: `['ab$$', 'c$d$']` should return `true`")
​
    def test_4(self):
        assert is_dollar_delete_equal(["b$$p", "$b$p"]) == True
        print("PASSED: `['b$$p', '$b$p']` should return `true`")
​
​
if __name__ == "__main__":

OUTPUT

Results will appear here.