Сравнение строк с символами возврата

Сравнение строк с символами возврата

Условие задачи

Даны две строки, состоящие только из ASCII-символов. Символ # означает возврат с удалением предыдущего символа. Проверьте, равны ли строки после применения всех возвратов.

Пример 1:

1
2
3

Вход: str1="xy#z", str2="xzz#"
Выход: true
Пояснение: обе строки превращаются в "xz".

Пример 2:

1
2
3

Вход: str1="xy#z", str2="xyz#"
Выход: false
Пояснение: строки превращаются в "xz" и "xy".

Пример 3:

1
2
3

Вход: str1="xp#", str2="xyz##"
Выход: true
Пояснение: обе строки превращаются в "x".

Пример 4:

1
2
3

Вход: str1="xywrrmp", str2="xywrrmu#p"
Выход: true
Пояснение: обе строки превращаются в "xywrrmp".

Решение

Идём с конца обеих строк. Для каждого указателя считаем встретившиеся # и пропускаем соответствующее число обычных символов, пока не получим следующий действующий символ.

Если действующие символы различаются или одна строка закончилась раньше другой, строки не равны. Если оба указателя одновременно вышли за начало строк, сравнение успешно. Промежуточные строки создавать не нужно.

Код

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

package main

import "fmt"

func nextValidCharacterIndex(value string, index int) int {
	backspaces := 0
	for index >= 0 {
		switch {
		case value[index] == '#':
			backspaces++
		case backspaces > 0:
			backspaces--
		default:
			return index
		}
		index--
	}
	return -1
}

func compareWithBackspaces(first, second string) bool {
	firstIndex, secondIndex := len(first)-1, len(second)-1

	for firstIndex >= 0 || secondIndex >= 0 {
		firstIndex = nextValidCharacterIndex(first, firstIndex)
		secondIndex = nextValidCharacterIndex(second, secondIndex)

		if firstIndex < 0 && secondIndex < 0 {
			return true
		}
		if firstIndex < 0 || secondIndex < 0 || first[firstIndex] != second[secondIndex] {
			return false
		}

		firstIndex--
		secondIndex--
	}

	return true
}

func main() {
	fmt.Println(compareWithBackspaces("xy#z", "xzz#"))
	fmt.Println(compareWithBackspaces("xy#z", "xyz#"))
	fmt.Println(compareWithBackspaces("xp#", "xyz##"))
	fmt.Println(compareWithBackspaces("xywrrmp", "xywrrmu#p"))
}

Вывод:

1
2
3
4

true
false
true
true

Временная сложность

Каждый символ обеих строк обрабатывается не более одного раза, поэтому временная сложность равна \(O(M+N)\), где \(M\) и \(N\) — длины строк.

Пространственная сложность

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).