leetcode-php/src/leetcode/BackspaceStringCompare.php at master · imajinyun/leetcode-php · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
<?php

declare(strict_types=1);

namespace leetcode;

class BackspaceStringCompare
{
    public static function backspaceCompare(string $s, string $t): bool
    {
        if (empty($s) || empty($t)) {
            return false;
        }
        $helper = static function (string &$s, int &$i) {
            $n = 0;
            while ($i >= 0 && ($n > 0 || $s[$i] === '#')) {
                $n = $s[$i] === '#' ? $n + 1 : $n - 1;
                $i--;
            }
            return $i >= 0 ? $s[$i] : '#';
        };
        [$i, $j] = [strlen($s) - 1, strlen($t) - 1];
        while ($i >= 0 || $j >= 0) {
            $p = $helper($s, $i);
            $q = $helper($t, $j);
            if ($p !== $q) {
                return false;
            }
            $i--;
            $j--;
        }

        return true;
    }

    public static function backspaceCompare2(string $s, string $t): bool
    {
        if (empty($s) || empty($t)) {
            return false;
        }
        [$i, $j] = [strlen($s) - 1, strlen($t) - 1];
        $m = $n = 0;
        while (true) {
            while ($i >= 0 && ($m > 0 || $s[$i] === '#')) {
                $m += $s[$i] === '#' ? 1 : -1;
                $i--;
            }
            while ($j >= 0 && ($n > 0 || $t[$j] === '#')) {
                $n += $t[$j] === '#' ? 1 : -1;
                $j--;
            }
            if ($i >= 0 && $j >= 0 && $s[$i] === $t[$j]) {
                $i--;
                $j--;
            } else {
                break;
            }
        }

        return $i === -1 && $j === -1;
    }

    public static function backspaceCompare3(string $s, string $t): bool
    {
        if (empty($s) || empty($t)) {
            return false;
        }
        $helper = static function (string $s, array $stack) {
            $n = strlen($s);
            for ($i = 0; $i < $n; $i++) {
                if ($s[$i] === '#') {
                    if (!$stack) {
                        continue;
                    }
                    array_pop($stack);
                } else {
                    array_push($stack, $s[$i]);
                }
            }
            return $stack;
        };
        [$p, $q] = [$helper($s, []), $helper($t, [])];

        return $p === $q;
    }
}