有限状态机详解与举例(leetcode 1023)

三特征

• 状态(state)总数是有限的
• 任意时刻只处于一种状态
• 某条件下会从一个状态转到下一个状态

四要素

• 当前状态：当前所处的状态
• 条件/事件：触发动作或转换的情况，例如输入
• 动作/转换：根据条件/事件，将一个状态转换到下一状态
• 下一状态：动作转换的下一状态，转换后这一状态就成了当前状态

注意项

• 状态不要漏掉
• 动作不要当做状态

举例

leetcode1023

如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 个字符。）

给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。

示例 1：

输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"

输出：[true,false,true,true,false]

示例：

"FooBar" 可以这样生成："F" + "oo" + "B" + "ar"。

"FootBall" 可以这样生成："F" + "oot" + "B" + "all".

"FrameBuffer" 可以这样生成："F" + "rame" + "B" + "uffer".

示例 2：

输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"

输出：[true,false,true,false,false]

解释：

"FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".

"FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".

示例 3：

输出：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"

输入：[false,true,false,false,false]

解释：

"FooBarTest" 可以这样生成："Fo" + "o" + "Ba" + "r" + "T" + "est".

 

提示：

1 <= queries.length <= 100

1 <= queries[i].length <= 100

1 <= pattern.length <= 100

所有字符串都仅由大写和小写英文字母组成。

来源：力扣（LeetCode）

链接：力扣

思路

建立pattern的有限自动机，以下标作为状态，附加-1、-2做初始状态与匹配失败状态，以要匹配的字符串作为输入（事件），判断最终状态是否为n-1。

输入：字符，之后的转换将根据字符串的大小写和是否匹配（输入有2*2=4种小情况）进行转换。

状态与转换：

初始状态-1：还没有输入，如果输入ss==pattern[0]，转换到状态i=0，如果输入ss!=patter[0]且ss isupper，转换到状态-2，否则不变

中间状态i(0=<i<n-1)：如果输入ss==pattern[i+1]，转换到状态i=i+1，如果输入ss!=pattern[i+1]且ss isupper，转换到状态-2，其他不变

匹配成功状态i(i==n-1):ss isuppper，转换到-2，ss islower 不变

匹配失败状态-2：任何输入都是-2

有限状态机图

代码

class Solution:
    def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
        n, state = len(pattern), -1
        def get_next(ss: str):
            nonlocal state
            if state == -2:
                return state
            elif state == -1 and ss == pattern[0]:
                state = 0
            elif state == -1 and ss != pattern[0] and ss.isupper():
                state = -2
            elif state == n-1 and ss.isupper():
                state = -2
            elif 0 <= state < n-1 and ss == pattern[state + 1]:
                state += 1
            elif 0 <= state < n-1 and ss != pattern[state + 1] and ss.isupper():
                state = -2
            return state
        ans = []
        for q in queries:
            for a in q:
                res = get_next(a)
            ans.append(res == n-1)
            state = -1
        return ans

合并了一些条件，写的全运行效率会高一点，使用其他语言可使用switch case更方便

可扩展状态机

上面的代码比较难看，不易扩展，一旦增加状态或事件，很麻烦

这里提出可扩展状态机，将状态与状态机解耦

有限状态机和状态相互依赖，单独实现具体状态类

有限状态机与状态

class Fsm:
    def __init__(self, state, pattern):
        self.state = state
        self.pattern = pattern
    def trans(self, ss):
        print("当前状态:", self.state.i)
        self.state = self.state.tran(ss, self)
        print("转换后状态:", self.state.i)
class State:
    fsm = Fsm(-1, "")
    def __init__(self, i):
        self.i = i
    def tran(self, ss, fsm):
        pass

具体状态

class Fail(State):
    def tran(self, ss, fsm):
        return self
class Success(State):
    def tran(self, ss, fsm):
        if ss.isupper():
            return Fail(-2)
        return self
class Normal(State):
    def tran(self, ss, fsm):
        if ss == fsm.pattern[self.i + 1]:
            if self.i + 1 == len(fsm.pattern) - 1:
                return Success(self.i + 1)
            return Normal(self.i + 1)
        if ss != fsm.pattern[self.i + 1] and ss.isupper():
            return Fail(-2)
        return self
class Init(State):
    def tran(self, ss, fsm):
        if ss == fsm.pattern[0]:
            return Normal(0)
        if ss != fsm.pattern[0] and ss.isupper():
            return Fail(-2)
        return self

这样，状态就可以随时增加了 ，方便扩展

这里有限状态机在初始化的时候就依赖了（初始）状态，而状态依赖有限状态机主要体现在转换的时候是否需要使用状态机的一些东西，如果不需要，可根据事件（这里是输入ss）转换，就没必要依赖了，如果需要的话（这里是pattern），可以通过传参或绑定的方式（可以在新状态产生后，将fsm绑定到当前有限状态机，tran函数就不用fsm了，使用self.fsm即可获取数据）。

更多python相关内容：【python总结】python学习框架梳理

更多内容：OJ网站题目分类，分难度整理笔记（leetcode、牛客网）

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。