Один интересный код-челлендж с Leetcode: поиск анаграмм в строке
На моих собеседованиях по программированию я часто использую упрощенную версию этой задачи с Leetcode. Даны две строки s и p, вернуть true, если s содержит анаграмму p. Мне нравится эта задача, потому что решение можно постепенно улучшать, и есть много чего обсудить. От алгоритмической сложности до оптимизации на уровне кэша процессора. Здесь я хочу рассказать, как решил эту задачу в первый раз. Самое затратное решение Первое решение, которое приходит в голову: давайте создадим список всех возможных анаграмм, а затем просто проверим, есть ли одна из них в строке s. Звучит просто, не так ли? Но есть несколько проблем с этим подходом. Во-первых, реализация эффективного алгоритма для генерации всех возможных перестановок уже является достаточно сложной задачей. А во-вторых, временная сложность итогового решения будет примерно O(s*p!). Факториал растет очень быстро: 3! == 6, 5! == 120, 10! == 3,628,800, и вы не захотите с этим иметь дело. ...