здравствуйте~ Уважаемые зрители и господа все~ Недавно алгоритм на LeetCode почти почистили (остальное сложно, не посмотрев ответ не сделаешь), пора подвести итог тому, что вы узнали в процессе Чистка вопросов Некоторые интересные точки знаний. Я полагаю, что все немного понимают React, и вы, возможно, видели подобное утверждение: «React рассматривает компоненты как конечный автомат (State Machines). Благодаря взаимодействию с пользователем достигаются различные состояния, а затем рендерится пользовательский интерфейс. , чтобы пользовательский интерфейс и данные оставались согласованными." Так что же такое конечный автомат?
Эта статья кратко представит концепцию конечного автомата и покажет его конкретное применение, ответив на алгоритм.Я надеюсь, вы сможете узнать больше об интересной модели конечного автомата.При работе со сложными состояниями в программировании есть новая опция~ Здесь это текст:
что такое конечный автомат
Конечный автомат(английский: конечный автомат, аббревиатура:FSM) также известен какАвтоматы с конечным состоянием, именуемыйГосударственный аппарат, представляет собой математическую модель, представляющую конечное число состояний и вариантов поведения, таких как переходы и действия между этими состояниями.
Вышеприведенный отрывок из Википедии, и он все еще выглядит немного абстрактно~ Проще говоря, есть такое устройство, пользователь продолжает вводить ввод, и устройство сообщает пользователю, является ли введенный ввод законным. На самом деле, в процессе программирования вы будете подвергаться этому в той или иной степени, просто не замечая этого. Например, регуляризация является типичным применением конечных автоматов. Прежде чем рассматривать конкретные примеры, нам также необходимо понять характеристики конечных автоматов:
Общее количество состояний ограничено.
В любой момент времени существует только одно состояние.
После срабатывания определенного условия он переходит из одного состояния в другое.
Хорошо~ вводится понятие конечного автомата,Эту статью можно закрывать!Выглядит скучно, не правда ли, не беда, поговорим о картинке:
Это типичная диаграмма конечного автомата, круг представляет состояние в конечном автомате, а двойной круг — это тоже состояние, но особое, это конечное состояние, которое является принимающим состоянием. Если конечное состояние конечного автомата остается в конечном состоянии в соответствии с вводом, это означает, что ввод является приемлемым и допустимым. Стрелки указывают переходы между состояниями, например, когда конечный автомат находится вS2состояние, введите 0 в конечный автомат, затем по стрелке состояние переходит вS1, введите 0, чтобы "перенести" вS2, то есть оставайтесь на месте, оставайтесь прежними. Обратите внимание, что когда вводится символ, отличный от 0 или 1, конечный автомат не имеет никакого перехода, который может адаптироваться к символу, тогда ввод может считаться недопустимым в это время.
OK~ До сих пор основные концепции конечного автомата были почти поняты.Следующее объединяет примеры, чтобы увидеть его практическое использование.
Применение конечного автомата
Как упоминалось выше, регулярность — это типичное применение конечных автоматов, поэтому мы могли бы также реализовать простой регулярный движок, который может возвращать, соответствует ли регулярное выражение строке в соответствии с входной строкой и регулярным выражением:
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
Вот оригинальный вопрос от LeetCode:44. Сопоставление подстановочных знаков, каждый может пожелать приостановить чтение и попытаться решить эту проблему. Идей для решения проблем на самом деле довольно много, но поскольку это регулярная корреляция, то конечный автомат определенно может решить эту проблему. Затем по примеру нарисуйте принципиальную схему конечного автомата, чтобы найти чувство:
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
Согласно регулярному выражениюp, этот конечный автомат можно нарисовать:
Как показано на рисунке выше, состояние конечного автомата в начале равноS0, когда персонажaПосле ввода состояние конечного автомата меняется сS0перейти кS1, а затем введите символ в конечный автоматa, но вS1В состоянии нет пути для передачи, поэтому ввод недействителен, возвратfalse.
Давайте рассмотрим еще один интересный пример:
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
На основе примера можно нарисовать этот конечный автомат:
Этот конечный автомат более интересен.Переход между состояниями больше не является единственной возможностью, а есть возможность перехода в разные состояния по одному и тому же входу. Анализ, начальное состояние конечного автоматаS0, введите символы в конечный автоматa,из-за*может соответствовать любой строке, то конечный автомат может либо «стоять на месте», либо двигаться вS1. Но конечный автомат в каждый момент времени находится только в одном состоянии, так что же нам делать? На самом деле можно предположить, что существует бесчисленное количество конечных автоматов для запуска.При возникновении ситуации ветвления запускается несколько конечных автоматов для передачи соответствующего состояния. Согласно этой идее, в это время нам нужно запустить два конечных автомата, один из которых находится в состоянииS0, другой вS1(отS0передано).
После ввода по одномуdceТри символа, оба автомата "стоят на месте", и вводится последний символb, согласно условиям перехода, первый конечный автомат может оставаться только на месте, а второй конечный автомат может либо переходить вS2, также может остаться на месте, поэтому снова откройте конечный автомат. Состояние третьего состоянияS3. Это конец ввода, проверьте запущенный конечный автомат и обнаружите, что состояние одного конечного автомата является окончательным, поэтому ввод допустим, возвратtrue.
Можно видеть, что если состояние одного конечного автомата является окончательным, то ввод является допустимым (то есть совпадение выполнено успешно). Теперь, когда у нас есть идея, пришло время описать ее в коде, можно попробовать написать соответствующую программу самостоятельно. Вот моя реализация:
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
// 连续的*是没意义的，算是简单的优化
p = p.replace(/\*+/g, '*');
// 正则对应状态机的描述
const map = {};
// 初始状态
let index = 0;
for (const token of p) {
map[index] = map[index] || {};
map[index][token] = true;
// 只要不是*，那只要匹配，一定能转移到下一个状态
if (token !== '*') index++;
}
// 最大的index，就是状态机的最终状态
const SUCCESS = index;
// 已启动状态机的集合，值为该状态机所在的状态
let set = new Set();
set.add(0);
for (let i = 0; i < s.length; i++) {
const newSet = new Set();
const token = s[i];
for (const status of set) {
// 如果状态机没有任何转移条件，那就没必要继续下面的判断，废弃这个状态机
if (!map[status]) continue;
// 原地踏步的情况
if (map[status]['*']) newSet.add(status);
// 匹配到对应字符，可以转移到下一个状态的情况
if (map[status]['?'] || map[status][token]) newSet.add(status + 1);
}
if (!newSet.size) return false;
// 用新的状态机集合取代旧的集合
set = newSet;
}
return set.has(SUCCESS);
};
Я добавил комментарии к коду и немного пройдусь по всему процессу~mapявляется описанием всего конечного автомата.mapКлюч — это соответствующее состояние, а значение — это объект, описывающий путь перехода (он же те самые стрелки).setпредставляет собой набор запущенных конечных автоматов.Поскольку все конечные автоматы на самом деле одинаковы, разница заключается в их текущем состоянии, поэтому значением коллекции является состояние конечного автомата. После этого необходимо пройти по входной строке, ввести символы один за другим в конечный автомат и выполнить переход конечного автомата. Наконец, оценивается, есть ли конечное состояние в запущенном конечном автомате, и можно ли вернуть результат~
Результат запуска в LeetCode следующий:
резюме
Вышеприведенный алгоритм допускает оптимизацию, например повторное использование активированного конечного автомата, но для лучшей читабельности кода соответствующая оптимизация не выполняется. Конечно, по результатам работы видно, что скорость работы алгоритма не очень идеальна, только лучше, чем 23% представлений.Чтобы погнаться за скоростью, целесообразнее решить проблему с идея динамического программирования. Но использование конечного автомата для решения проблемы, идея довольно ясна, и она также может углубить понимание конечного автомата. В будущем, если вы столкнетесь со сложным переключением состояний и обслуживанием, вы можете рассмотреть возможность использования конечного автомата для решения этой проблемы.
Выше содержание полного текста! Конечные автоматы на самом деле довольно интересные модели, широко используемые во фронтенде, бэкенде и даже компиляторах. Эта статья лишь кратко знакомит с соответствующими концепциями и их приложениями.Для подробного содержания вам необходимо прочитать соответствующие книги~
Спасибо всем судьям за то, что увидели это, легче сказать, чем сделать, надеюсь, эта статья будет вам полезна~ Спасибо!