CodingGyan

Backspace String Compare

medium Strings

Problem

Two words are typed into an empty editor. The character # means backspace: it deletes the letter before it, and does nothing if the editor is empty. Print true if both words give the same text, else false.

Constraints

  • 1 <= length <= 200
  • lowercase letters and #

Examples

Input

ab#c ad#c

Output

true

Solutions

Best approachTime O(n)Space O(1)

We read from the right. A # means skip the next real letter, so we count skips. We compare the real letters one by one and never build the final texts. O(n) time, O(1) memory.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Compare typed text.
 * Input   : Two words.
 * Output  : true or false.
 * Approach: Two pointers.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        private static int nextIndex(String t, int i) {
            int skip = 0;
            while (i >= 0) {
                if (t.charAt(i) == '#') {
                    skip++;
                } else if (skip > 0) {
                    skip--;
                } else {
                    break;
                }
                i--;
            }
            return i;
        }

    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(String a, String b) {
        // Step 1: Walk both words from the end. A # tells us to skip letters, so no extra text is built.
        int i = nextIndex(a, a.length() - 1);
        int j = nextIndex(b, b.length() - 1);
        while (i >= 0 && j >= 0) {
            // Step 2: The next real letters must be equal.
            if (a.charAt(i) != b.charAt(j)) {
                return false;
            }
            i = nextIndex(a, i - 1);
            j = nextIndex(b, j - 1);
        }
        // Step 3: Both words must end at the same time.
        return i < 0 && j < 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. Why is reading from the right easier?
  2. What if skip is bigger than the letters left?

Try these next