844. Backspace String Compare

二刷 06/2022
Version #2 Two Pointers

需要注意的细节很多

思路就是从后往前走直到第一个确定不会被skip的character，然后比较

写了一个bug就是终止条件是ps >= 0 && pt >= 0有一个反例就是

"nzp#o#g"
"b#nzp#o#g"

最后的b#是没有被检测的

所以终止条件应该是ps >= 0 || pt >= 0

Time O(M + N)

Space O(1)

class {

    public boolean backspaceCompare(String s, String t) {

        int ps = s.length() - 1, pt = t.length() - 1;

        int sBackspaces = 0;

        int tBackspaces = 0;

        while (ps >= 0 || pt >= 0) {

            while ((ps >= 0 && s.charAt(ps) == '#') || sBackspaces > 0) {

                if (ps >= 0 && s.charAt(ps) == '#') {

                    sBackspaces++;

                    ps--;

                } else {

                    sBackspaces--;

                    ps = ps == -1 ? -1 : ps - 1;

                }

            }

            while ((pt >= 0 && t.charAt(pt) == '#') || tBackspaces > 0) {

                if (pt >= 0 && t.charAt(pt) == '#') {

                    tBackspaces++;

                    pt--;

                } else {

                    tBackspaces--;

                    pt = pt == -1 ? -1 : pt - 1;

                }

            }

            // System.out.printf("ps=%d, pt=%d\n", ps, pt);

            if (ps >= 0 && pt >= 0 && s.charAt(ps) != t.charAt(pt)) {

                return false;

            }

            ps--;

            pt--;

        }

        // System.out.printf("ps=%d, pt=%d\n", ps, pt);

        return ps == pt;

    }

}

一刷
Version #1 Stack
Time O(m + n)
Space O(m + n)

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

private String transform(String str) {
        if (str == null) {
return "";
}
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '#') {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(str.charAt(i));
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.poll());
}
return sb.toString();
}
}