Перестановка строки

Перестановка строки

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

Даны строка и шаблон из ASCII-символов. Определите, содержит ли строка какую-либо перестановку символов шаблона.

Перестановка получается изменением порядка символов. Например, у строки abc есть шесть перестановок: abc, acb, bac, bca, cab и cba.

Пример 1:

1
2
3

Вход: строка="oidbcaf", шаблон="abc"
Выход: true
Пояснение: строка содержит "bca" — перестановку шаблона.

Пример 2:

1
2
3

Вход: строка="odicf", шаблон="dc"
Выход: false
Пояснение: строка не содержит перестановку шаблона.

Пример 3:

1
2
3

Вход: строка="bcdxabcdy", шаблон="bcdyabcdx"
Выход: true
Пояснение: строка и шаблон являются перестановками друг друга.

Пример 4:

1
2
3

Вход: строка="aaacb", шаблон="abc"
Выход: true
Пояснение: строка содержит перестановку "acb".

Решение

Сначала подсчитаем частоты всех символов шаблона. Затем будем перемещать по строке окно длиной, равной длине шаблона:

  1. Если входящий символ есть в таблице, уменьшаем его частоту. Нулевая частота означает, что все вхождения этого символа совпали.
  2. Когда совпали все различные символы шаблона, окно содержит искомую перестановку.
  3. Достигнув нужного размера окна, удаляем его левый символ. Если этот символ относится к шаблону, восстанавливаем его частоту и при необходимости уменьшаем число полных совпадений.

Код

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

package main

import "fmt"

func containsPermutation(text, pattern string) bool {
	if len(pattern) == 0 || len(pattern) > len(text) {
		return false
	}

	frequencies := make(map[byte]int)
	for index := 0; index < len(pattern); index++ {
		character := pattern[index]
		frequencies[character]++
	}

	windowStart := 0
	matched := 0

	for windowEnd := 0; windowEnd < len(text); windowEnd++ {
		character := text[windowEnd]
		if _, ok := frequencies[character]; ok {
			frequencies[character]--
			if frequencies[character] == 0 {
				matched++
			}
		}
		if matched == len(frequencies) {
			return true
		}

		if windowEnd >= len(pattern)-1 {
			leftCharacter := text[windowStart]
			windowStart++
			if _, ok := frequencies[leftCharacter]; ok {
				if frequencies[leftCharacter] == 0 {
					matched--
				}
				frequencies[leftCharacter]++
			}
		}
	}

	return false
}

func main() {
	fmt.Println("Перестановка существует:", containsPermutation("oidbcaf", "abc"))
	fmt.Println("Перестановка существует:", containsPermutation("odicf", "dc"))
	fmt.Println("Перестановка существует:", containsPermutation("bcdxabcdy", "bcdyabcdx"))
	fmt.Println("Перестановка существует:", containsPermutation("aaacb", "abc"))
}

Вывод:

1
2
3
4

Перестановка существует: true
Перестановка существует: false
Перестановка существует: true
Перестановка существует: true

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

Построение таблицы занимает \(O(M)\), а проход по строке — \(O(N)\). Общая временная сложность равна \(O(N+M)\).

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

В худшем случае все символы шаблона различны, поэтому пространственная сложность равна \(O(M)\).