Строки

Строка (string) в контексте алгоритмов — последовательность символов, хранящаяся как массив символов (или immutable объект); работа со строками включает поиск, замену, сравнение и разбор паттернов.

Зачем нужно

Строки — один из самых частых типов данных в задачах: парсинг, поиск подстрок, анаграммы, палиндромы. Знание алгоритмов на строках (sliding window, два указателя, хеширование) позволяет избегать O(n^2) решений. В JS строки immutable, что важно для понимания сложности операций конкатенации.

Где используется

  • Поиск подстрок: поисковые движки, grep, git grep
  • Валидация: email, URL, номера карт (regex)
  • Биоинформатика: ДНК-последовательности (ACGT)
  • Компиляторы: лексический анализ, токенизация

Основной контент

Строки в JavaScript

// Строки immutable: каждая операция создаёт новую строку
const s = "hello";
s[0] = 'H'; // нет эффекта! s === "hello"

// Длина строки — O(1) (кэшировано)
s.length; // 5

// Доступ по индексу — O(1)
s[0];       // 'h'
s.at(-1);   // 'o' (ES2022)
s.charAt(1); // 'e'

// Иммутабельность: concat, slice, replace — новые строки O(n)
const s2 = s + " world"; // O(n) — создаёт новую строку

Важные алгоритмические операции

// 1. Проверка палиндрома — O(n)
function isPalindrome(s) {
  let lo = 0, hi = s.length - 1;
  while (lo < hi) {
    if (s[lo++] !== s[hi--]) return false;
  }
  return true;
}

// 2. Анаграммы — O(n)
function isAnagram(s1, s2) {
  if (s1.length !== s2.length) return false;
  const count = {};
  for (const ch of s1) count[ch] = (count[ch] || 0) + 1;
  for (const ch of s2) {
    if (!count[ch]) return false;
    count[ch]--;
  }
  return true;
}

// 3. Longest common prefix — O(n*m)
function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1); // укорачиваем
    }
  }
  return prefix;
}

// 4. Подсчёт частот символов — O(n)
function charFreq(s) {
  return [...s].reduce((acc, ch) => {
    acc[ch] = (acc[ch] || 0) + 1;
    return acc;
  }, {});
}

Конкатенация строк: O(n^2) vs O(n)

// Медленно: O(n²) — n итераций, каждая создаёт новую строку размера i
let result = '';
for (const word of words) {
  result += word; // O(n) на каждую итерацию → всего O(n²)
}

// Быстро: O(n) — join создаёт одну строку
const result2 = words.join('');

// Или Array.push + join
const parts = ;
for (const word of words) parts.push(word);
const result3 = parts.join('');

Кодировки: ASCII, Unicode, UTF-8

// ASCII: символы 0-127, 'a'.charCodeAt(0) === 97
'a'.charCodeAt(0); // 97
String.fromCharCode(65); // 'A'

// Unicode: JS использует UTF-16
'😀'.length; // 2 (суррогатная пара!)
[...'😀'].length; // 1 (правильно!)

// Сравнение строк: лексикографическое
'apple' < 'banana'; // true
'Z' < 'a'; // true ('Z'=90, 'a'=97 в ASCII)

Поиск подстрок

// Наивный O(n*m)
s.includes('pattern');   // O(n*m)
s.indexOf('pattern');    // O(n*m), возвращает индекс или -1

// KMP алгоритм — O(n+m) (теоретически, в CP)
// Rabin-Karp — O(n+m) средний случай с хешированием

Частые ошибки

  • Конкатенация в цикле через += — O(n^2); используй массив + join.
  • Считать string.length в unicode-символах — для emoji и emoji-флагов length считает кодовые единицы UTF-16, а не символы.
  • Изменять строку как массив: строки immutable в JS — присваивание по индексу ничего не делает.
  • Сравнивать строки с == в Java/Python/C++ — в JS это работает, но в других языках — нет.

Связанные темы

Ресурсы