Алгоритмы - Строки

Этот код решает задачу проверки, являются ли две строки анаграммами друг друга.
Анаграммы - это слова или фразы, состоящие из одних и тех же букв, но в разном порядке.

Алгоритм решения

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

Временная сложность: O(n), где n - длина строк. Это происходит потому, что мы проходим по каждой строке один раз для заполнения словарей, а затем еще раз проходим по словарю для сравнения.

Пространственная сложность: O(k), где k - размер алфавита (количество уникальных символов в строках). В худшем случае, когда все символы в строках уникальны, это может быть O(n), но обычно k намного меньше n.

func isAnagram(s1, s2 string) bool {
    if len(s1) != len(s2) {
    return false
    }

    s1Rune := make(map[rune]int)
    s2Rune := make(map[rune]int)

    for _, r := range s1 {
    s1Rune[r]++
    }

    for _, r := range s2 {
    s2Rune[r]++
    }

    for r, count := range s1Rune {
    if count != s2Rune[r] {
    return false
    }
    }

    return true
}

Этот код реализует функцию strStr, которая решает задачу нахождения индекса первого вхождения подстроки (needle) в строку (haystack). Это аналог функции indexOf в некоторых языках программирования.

Алгоритм решения

Проверяем краевые случаи:
- Если needle пустая, возвращаем 0 (пустая строка всегда считается найденной в начале любой строки).
- Если haystack короче needle, возвращаем -1 (невозможно найти).
Проходим по строке haystack, используя скользящее окно размером с needle:
- Для каждой позиции i в haystack проверяем, совпадает ли подстрока haystack[i:i+len(needle)] с needle.
- Если совпадение найдено, возвращаем индекс i.
Если после прохода по всей строке совпадение не найдено, возвращаем -1.

Временная сложность: O(n * m), где n - длина haystack, m - длина needle.

Пространственная сложность: O(1), так как используется только фиксированное количество дополнительных переменных, независимо от размера входных строк.

func strStr(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}

	if len(haystack) < len(needle) {
		return -1
	}

	for i := 0; i <= len(haystack)-len(needle); i++ {
		if haystack[i:i+len(needle)] == needle {
			return i
		}
	}

	return -1
}

Этот код генерирует все возможные правильные скобочные последовательности заданной длины n. Правильная скобочная последовательность - это строка, содержащая только скобки '(' и ')', где каждая открывающая скобка имеет соответствующую закрывающую, и они правильно вложены.

Алгоритм решения

Функция generateScobs инициализирует пустой слайс для результатов и вызывает вспомогательную рекурсивную функцию.
Функция generateHelper использует рекурсию с бэктрекингом:
- Базовый случай: если все скобки использованы, добавляем текущую последовательность в результат.
- Рекурсивные случаи:
  - Если есть неиспользованные открывающие скобки, добавляем '(' и рекурсивно вызываем функцию.
  - Если закрывающих скобок осталось больше, чем открывающих, добавляем ')' и рекурсивно вызываем функцию.

Временная сложность: O(4^n / √n)
- Это приближение n-го числа Каталана, которое определяет количество правильных скобочных последовательностей.
Пространственная сложность: O(n)
- Обусловлена глубиной рекурсии и длиной хранимых строк.

func generateScobs(n int) []string {
	result := make([]string, 0)
	generateHelper(n, n, n, &result, "")
	return result
}

func generateHelper(n, left, right int, result *[]string, current string) {
	if left == 0 && right == 0 && current != "" {
		*result = append(*result, current)
		return
	}

	if left > 0 {
		generateHelper(n, left-1, right, result, current+"(")
	}

	if right > left {
		generateHelper(n, left, right-1, result, current+")")
	}
}

Этот код реализует функцию isSubsequence, которая проверяет, является ли строка s подпоследовательностью строки t. Подпоследовательность - это последовательность символов, которая появляется в той же последовательности в другой строке, но не обязательно непрерывно.

Алгоритм решения

Проверка краевых случаев:
- Если s пустая или равна t, возвращаем true.
- Если s длиннее t, или они равной длины, но не равны, или t пустая, возвращаем false.
Преобразование строк в слайсы рун для корректной обработки Unicode-символов.
Итерация по символам строки t:
- Если текущий символ совпадает с символом в s на позиции курсора, увеличиваем курсор.
- Если курсор достиг конца s, возвращаем true (вся подпоследовательность найдена).
Если после прохода по всей строке t не все символы s найдены, возвращаем false.

Временная сложность: O(t), где t - длина строки t
- В худшем случае алгоритм проходит по всей строке t один раз.
Пространственная сложность: O(m+n), где m и n - длины строк s и t соответственно
- Создаются два новых слайса рун для хранения символов обеих строк.

func isSubsequence(s string, t string) bool {
	if s == t || s == "" {
		return true
	}
	if len(s) > len(t) || t == "" {
		return false
	}

	rS := []rune(s)
	rT := []rune(t)

	cursor := 0
	for _, c := range rT {
		if rS[cursor] == c {
			cursor++
		}

		if cursor == len(rS) {
			return true
		}
	}

	return false
}

Функция checkCorrectScobs проверяет корректность строки, содержащей только круглые скобки, и возвращает количество правильно закрытых пар скобок и булево значение, указывающее на общую корректность последовательности.

Алгоритм решения

Инициализация переменных:
- isCorrect: флаг корректности последовательности
- count: счетчик правильно закрытых пар скобок
- countOpen: счетчик открытых скобок
Итерация по строке:
- Если встречается открывающая скобка '(', увеличиваем countOpen
- Если встречается закрывающая скобка ')':
  - Проверяем, есть ли открытые скобки (countOpen > 0)
  - Если нет, возвращаем (0, false)
  - Если есть, уменьшаем countOpen и увеличиваем count
После итерации:
- Если остались незакрытые скобки (countOpen != 0), устанавливаем isCorrect = false
Возвращаем count и isCorrect

Временная сложность: O(n)
- Где n - длина входной строки
- Алгоритм проходит по строке ровно один раз
Пространственная сложность: O(1)
- Используется постоянное количество дополнительной памяти, независимо от размера входной строки

func checkCorrectScobs(str string) (int, bool) {
	isCorrect := true
	count := 0
	countOpen := 0

	for i := 0; i < len(str); i++ {
		if str[i] == '(' {
			countOpen++
			continue
		}

		if str[i] == ')' {
			if countOpen == 0 {
				return 0, false
			}
			countOpen--
			count++
		}
	}

	if countOpen != 0 {
		isCorrect = false
	}

	return count, isCorrect
}

Функция isPolindrom проверяет, являются ли две входные строки палиндромами друг друга. То есть, является ли вторая строка обратной первой.

Алгоритм решения

Проверка длины строк:
- Если длины строк не равны, возвращаем false
Преобразование строк в слайсы рун:
- Это позволяет корректно работать с Unicode-символами
Итерация по символам:
- Сравниваем символы с начала первой строки с символами с конца второй строки
- Если находим несоответствие, возвращаем false
Если все символы совпали, возвращаем true

Временная сложность: O(n)
- Где n - длина строки
- Алгоритм проходит по половине символов строки
Пространственная сложность: O(n)
- Создаются два новых слайса рун, каждый длиной n

func isPolindrom(s1, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}

	s1Rune := []rune(s1)
	s2Rune := []rune(s2)

	for i := 0; i <= len(s1Rune)/2+1; i++ {
		if s1Rune[i] != s2Rune[len(s2Rune)-i-1] {
			return false
		}
	}

	return true
}

Функция isPalindrome проверяет, является ли заданная строка палиндромом, игнорируя регистр букв и не учитывая не буквенно-цифровые символы.

Алгоритм решения

Инициализация указателей:
- Устанавливаем левый указатель на начало строки, правый - на конец
Итерация по строке:
- Сравниваем символы с левого и правого концов строки
- Приводим символы к нижнему регистру
- Пропускаем не буквенно-цифровые символы
- Если символы не совпадают, возвращаем false
- Сдвигаем указатели к центру строки
Проверка завершена:
- Если все символы совпали, возвращаем true

Временная сложность: O(n)
- Где n - длина входной строки
- Алгоритм проходит по строке только один раз
Пространственная сложность: O(1)
- Используется постоянное количество дополнительной памяти, независимо от размера входной строки

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1

	for left < right {
		leftChar := unicode.ToLower(rune(s[left]))
		rightChar := unicode.ToLower(rune(s[right]))

		if !isAlphanumeric(leftChar) {
			left++
			continue
		}
		if !isAlphanumeric(rightChar) {
			right--
			continue
		}

		if leftChar != rightChar {
			return false
		}

		left++
		right--
	}

	return true
}

func isAlphanumeric(r rune) bool {
	return unicode.IsLetter(r) || unicode.IsDigit(r)
}

Функция isValid проверяет, является ли входная строка корректным выражением с правильно расставленными скобками трех типов: круглыми (), квадратными [] и фигурными {}.

Алгоритм решения

Инициализация:
- Создаем пустой стек для хранения открывающих скобок
- Определяем map для сопоставления закрывающих скобок с открывающими
Итерация по строке:
- Если символ - открывающая скобка, добавляем его в стек
- Если символ - закрывающая скобка:
  - Проверяем, пуст ли стек или не соответствует ли последняя открывающая скобка в стеке
  - Если условие выполняется, возвращаем false
  - Иначе удаляем последнюю открывающую скобку из стека
Проверка завершена:
- Возвращаем true, если стек пуст (все скобки закрыты)

Временная сложность: O(n)
- Где n - длина входной строки
- Алгоритм проходит по строке только один раз
Пространственная сложность: O(n)
- В худшем случае (когда все символы - открывающие скобки) стек может содержать все n символов

func isValid(s string) bool {
	stack := make([]rune, 0)
	parentheses := map[rune]rune{')': '(', ']': '[', '}': '{'}

	for _, c := range s {
		if c == '(' || c == '[' || c == '{' {
			stack = append(stack, c)
		} else if len(stack) == 0 || parentheses[c] != stack[len(stack)-1] {
			return false
		} else {
			stack = stack[:len(stack)-1]
		}
	}

	return len(stack) == 0
}

Функция longestPalindrome находит самый длинный палиндром в заданной строке.

Алгоритм решения

Проверка граничных случаев:
- Если длина строки меньше 2, возвращаем саму строку
Итерация по каждому символу строки:
- Для каждого символа проверяем палиндромы с нечетной длиной (центр - текущий символ)
- Для каждого символа проверяем палиндромы с четной длиной (центр - между текущим и следующим символом)
- Используем вспомогательную функцию expandAroundCenter для расширения палиндрома
- Обновляем информацию о самом длинном найденном палиндроме
Возвращаем найденный самый длинный палиндром

Временная сложность: O(n^2)
- n - длина входной строки
- Для каждого символа мы можем расширяться до краев строки
Пространственная сложность: O(1)
- Используется постоянное количество дополнительной памяти

func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}

	start, maxLength := 0, 1

	for i := 0; i < len(s); i++ {
		// Проверяем палиндромы с нечетной длиной
		len1 := expandAroundCenter(s, i, i)
		// Проверяем палиндромы с четной длиной
		len2 := expandAroundCenter(s, i, i+1)

		length := max(len1, len2)
		if length > maxLength {
			start = i - (length-1)/2
			maxLength = length
		}
	}

	return s[start : start+maxLength]
}

func expandAroundCenter(s string, left, right int) int {
	for left >= 0 && right < len(s) && s[left] == s[right] {
		left--
		right++
	}
	return right - left - 1
}

Функция lengthOfLongestSubstring находит длину самой длинной подстроки без повторяющихся символов в заданной строке.

Алгоритм решения

Проверка на пустую строку
Преобразование строки в массив рун (для корректной работы с Unicode)
Инициализация переменных:
- subLengs - длина самой длинной найденной подстроки
- curSubRunes - карта для хранения последних позиций символов
Использование техники "скользящего окна":
- Проход по строке с двумя указателями: left и right
- Если символ уже встречался в текущем окне, сдвигаем левую границу
- Обновление позиции текущего символа в карте
- Обновление максимальной длины подстроки, если текущее окно больше
Возврат длины самой длинной подстроки

Временная сложность: O(n)
- n - длина входной строки
- Алгоритм проходит по строке один раз
Пространственная сложность: O(k)
- k - размер алфавита (максимальное количество уникальных символов)
- В худшем случае может быть O(min(n, m)), где m - размер используемого алфавита

func lengthOfLongestSubstring(s string) int {
	if s == "" {
		return 0
	}

	runes := []rune(s)
	left, subLengs := 0, 0
	curSubRunes := make(map[rune]int)

	for right := 0; right < len(runes); right++ {
		// Если текущий символ уже встречался в текущем окне, сдвигаем левую границу окна.
		if idx, ok := curSubRunes[runes[right]]; ok && idx >= left {
			left = idx + 1
		}
		curSubRunes[runes[right]] = right // пишем текущий символ
		// если текущее окно больше предыдущего обновляем
		subLengs = max(subLengs, right-left+1)
	}

	return subLengs
}

Дано две строки s1 и s2. Необходимо определить, содержит ли строка s2 перестановку строки s1 в качестве подстроки. Задача известна как "Permutation in String".

Алгоритм решения

Проверяем, что длина s1 не превышает длину s2. Если превышает, возвращаем false.
Создаем два массива count1 и count2 размером 256 для подсчета частоты символов.
Заполняем count1 частотами символов из s1 и count2 частотами символов из первого окна s2 длиной len(s1).
Проверяем, равны ли count1 и count2. Если да, возвращаем true.
Используем метод скользящего окна для проверки остальной части s2:
- Уменьшаем счетчик для символа, выходящего из окна.
- Увеличиваем счетчик для нового символа, входящего в окно.
- Сравниваем count1 и count2. Если равны, возвращаем true.
Если ни одно окно не дало совпадения, возвращаем false.

Особенности решения

Работает с расширенным набором символов UTF-8, включая эмодзи и другие Unicode символы.
Эффективно использует метод скользящего окна для оптимизации производительности.
Не требует сортировки или преобразования строк, что улучшает эффективность.
Подходит для работы с большими строками благодаря линейной временной сложности.

Временная сложность: O(n), где n - длина строки s2. Мы проходим по s2 один раз.
Пространственная сложность: O(1), так как используются массивы фиксированного размера (256) независимо от входных данных.

func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }

    // Создаем слайсы для подсчета символов
    count1 := make([]int, 256)
    count2 := make([]int, 256)

    // Заполняем count1 для s1 и первого окна s2
    for i := 0; i < len(s1); i++ {
        count1[s1[i]]++
        count2[s2[i]]++
    }

    // Проверяем первое окно
    if isEqual(count1, count2) {
        return true
    }

    // Скользящее окно для остальной части s2
    for i := len(s1); i < len(s2); i++ {
        count2[s2[i-len(s1)]]--
        count2[s2[i]]++
        if isEqual(count1, count2) {
            return true
        }
    }

    return false
}

func isEqual(count1, count2 []int) bool {
    for i := 0; i < 256; i++ {
        if count1[i] != count2[i] {
            return false
        }
    }
    return true
}

Функция simplifyPath преобразует абсолютный путь в файловой системе в канонический путь, удаляя избыточные элементы и нормализуя структуру.

Алгоритм решения

Разделение входного пути на компоненты с помощью strings.Split
Инициализация стека для хранения валидных компонентов пути
Итерация по компонентам пути:
- Игнорирование пустых компонентов и "." (текущая директория)
- Обработка ".." (переход на уровень выше) путем удаления последнего элемента из стека
- Добавление валидных компонентов в стек
Сборка результирующего пути из элементов стека

Временная сложность: O(n)
- n - количество компонентов в пути
- Один проход по всем компонентам пути
Пространственная сложность: O(n)
- В худшем случае стек может содержать все компоненты пути

func simplifyPath(path string) string {
    // Разделяем путь на компоненты
    components := strings.Split(path, "/")
    stack := []string{}

    for _, component := range components {
        switch component {
        case "", ".":
            // Игнорируем пустые компоненты и текущую директорию
            continue
        case "..":
            // Переходим на уровень выше, если это возможно
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        default:
            // Добавляем валидный компонент пути
            stack = append(stack, component)
        }
    }

    // Собираем упрощенный путь
    result := "/" + strings.Join(stack, "/")
    return result
}

Функция compress выполняет сжатие строки, заменяя последовательности повторяющихся символов на символ и количество его повторений. Сжатие выполняется "на месте", модифицируя входной массив байтов.

Алгоритм решения

Проверка на короткие входные данные (длина 0 или 1)
Инициализация индекса записи и счетчика повторений
Итерация по символам строки:
- Подсчет последовательных повторений символа
- При смене символа или достижении конца строки:
  - Запись символа
  - Запись количества повторений (если больше 1)
  - Обновление индекса записи
Возврат новой длины сжатой строки

Временная сложность: O(n)
- n - длина входной строки
- Один проход по всем символам
Пространственная сложность: O(1)
- Модификация выполняется "на месте"
- Используется фиксированное количество дополнительных переменных

func compress(chars []byte) int {
    if len(chars) <= 1 {
        return len(chars)
    }

    writeIndex := 0
    count := 1

    for i := 1; i <= len(chars); i++ {
        if i < len(chars) && chars[i] == chars[i-1] {
            count++
        } else {
            chars[writeIndex] = chars[i-1]
            writeIndex++

            if count > 1 {
                countStr := strconv.Itoa(count)
                for _, digit := range countStr {
                    chars[writeIndex] = byte(digit)
                    writeIndex++
                }
            }
            count = 1
        }
    }

    return writeIndex
}

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

Пример:

Входная строка: AAABCCCCCDD

Результат: A3BC5D2

Функция должна возвращать ошибку, если на вход приходит недопустимая строка (содержащая символы, отличные от заглавных латинских букв).

Алгоритм решения

Алгоритм решения задачи состоит из следующих шагов:

Проверяем, что строка не пуста. Если строка пуста, возвращаем пустую строку.
Проверяем, что все символы в строке являются заглавными латинскими буквами. Если нет, возвращаем ошибку.
Инициализируем переменные для хранения текущего символа, счетчика повторений и результирующей строки.
Проходим по строке, начиная со второго символа:
- Если текущий символ совпадает с предыдущим, увеличиваем счетчик.
- Если символ отличается, добавляем предыдущий символ и его количество (если оно больше 1) в результат, затем обновляем текущий символ и сбрасываем счетчик.
После завершения цикла добавляем последний символ и его количество (если оно больше 1) в результат.
Возвращаем полученную сжатую строку.

Временная сложность: O(n), где n - длина входной строки.

Мы проходим по строке ровно один раз, выполняя константное количество операций для каждого символа.

Пространственная сложность: O(n) в худшем случае.

В худшем случае, когда все символы в строке различны (например, "ABCDEF"), результирующая строка будет иметь примерно такую же длину, как и входная. В лучшем случае (например, для строки с большим количеством повторений, как "AAAAAA"), пространственная сложность может быть значительно меньше O(n).

func CompressString(s string) (string, error) {
    if len(s) == 0 {
        return "", nil
    }

    // Проверка на допустимые символы (только заглавные латинские буквы)
    for _, char := range s {
        if !unicode.IsUpper(char) || !unicode.IsLetter(char) {
            return "", errors.New("строка содержит недопустимые символы")
        }
    }

    var result string
    count := 1
    currentChar := s[0]

    // Проходим по строке начиная со второго символа
    for i := 1; i < len(s); i++ {
        if s[i] == currentChar {
            // Если текущий символ совпадает с предыдущим, увеличиваем счетчик
            count++
        } else {
            // Если символ отличается, добавляем предыдущий символ и его количество в результат
            result += string(currentChar)
            if count > 1 {
                result += strconv.Itoa(count)
            }
            // Сбрасываем счетчик и обновляем текущий символ
            currentChar = s[i]
            count = 1
        }
    }

    // Добавляем последний символ и его количество
    result += string(currentChar)
    if count > 1 {
        result += strconv.Itoa(count)
    }

    return result, nil
}

Даны две строки s и t одинаковой длины. Необходимо определить, можно ли преобразовать строку s в строку t, выполнив не более одного циклического сдвига некоторого подотрезка строки s. Циклический сдвиг подотрезка [l, r] означает перемещение символов в этом подотрезке либо влево, либо вправо на одну позицию по кругу.

Алгоритм решения

Проверить, что длины строк s и t одинаковы. Если нет, вернуть false.
Использовать два указателя l и r для нахождения несовпадающего подотрезка строк s и t.
Если все символы совпадают, вернуть true.
Если l >= len(s)-r, то невозможно сделать циклический сдвиг, вернуть false.
Проверить возможность циклического сдвига влево и вправо для несовпадающего подотрезка.
Если ни один из сдвигов не приводит к совпадению, вернуть false.

Временная сложность: O(n), где n - длина строки. Алгоритм проходит по строкам только один раз.
Пространственная сложность: O(1), так как используется только несколько дополнительных переменных.

func canTransform(s, t string) bool {
    if len(s) != len(t) {
        return false
    }

    l, r := 0, len(s)-1

    // Находим первое несовпадение слева
    for l <= r && s[l] == t[l] {
        l++
    }
    // Находим первое несовпадение справа
    for l <= r && s[r] == t[r] {
        r--
    }

    // Если все символы совпадают, возвращаем true
    if l > r {
        return true
    }

    // Проверяем, можно ли сделать циклический сдвиг влево
    if canShiftLeft(s[l:r+1], t[l:r+1]) {
        return true
    }

    // Проверяем, можно ли сделать циклический сдвиг вправо
    return canShiftRight(s[l:r+1], t[l:r+1])
}

func canShiftLeft(s, t string) bool {
	for i := 0; i < len(s); i++ {
		// Выражение (i+1)%len(s) используется для циклического перехода в конец строки, когда i+1 становится равным длине строки.
		if s[i] != t[(i+1)%len(s)] {
			return false
		}
	}
	return true
}

func canShiftRight(s, t string) bool {
	for i := 0; i < len(s); i++ {
		// Выражение (i-1+len(s))%len(s) используется для:
		//1. Добавления len(s) к i-1, чтобы избежать отрицательных индексов.
		//2. Использования операции % для циклического перехода в конец строки.
		if s[i] != t[(i-1+len(s))%len(s)] {
			return false
		}
	}
	return true
}

Алгоритмы - Строки

Анаграмма

Алгоритм решения

Индекс первого вхождения подстроки

Алгоритм решения

Генерация всех возможных комбинаций скобочек

Алгоритм решения

Проверка подпоследовательности

Алгоритм решения

Проверка корректности скобочной последовательности

Алгоритм решения

Палиндромы

Алгоритм решения

Проверка строки с пробелами и большими буквами на палиндром

Алгоритм решения

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

Алгоритм решения

Поиск самого длинного палиндрома в строке

Алгоритм решения

Поиск длины самой длинной подстроки без повторяющихся символов

Алгоритм решения

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

Алгоритм решения

Особенности решения

Упрощение пути в файловой системе

Алгоритм решения

Сжатие строки (байт)

Алгоритм решения

Сжатие последовательности символов

Алгоритм решения

Циклический сдвиг подстроки

Алгоритм решения