目录
三个特征
四要素
注意事项
举个例子
leetcode1023
想法
代码
可扩展状态机
三个特征状态(state )的总数在任何有限的时间点只是一个状态(在某个条件下从一个状态转换到下一个状态) (当前状态)；条件/事件)。在触发动作或转换的情况下，例如输入动作/转换(interfact )条件注意事项请不要错过状态。 操作不应用作状态示例。 例如，如果可以在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”那样被生成。
可以像“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]
说明：
“反馈测试”可以被生成为“fo”“o”“ba”“r”“t”“est”这样的形式。
提示：
1=queries.length=100
1=queries[i].length=100
1=pattern.length=100
所有字符串仅由大小写的英文字母组成。
资料来源：力扣)。
链接：力量按钮
构建构想pattern的有限自动机，将以下标签作为状态，附加-1、-2形成初始状态和对照失败状态，将对照的字符串作为输入(事件)，判断最终状态是否为n-1。
输入：字符，随后的转换取决于字符串的大小写是否一致(输入可以是2*2=4种较小的类型)。
状态和转换：
初始状态-1:还没有输入。 输入ss==pattern[0]将转换为状态i=0，输入ss！=patter[0]且转移到ss isupper、状态-2，否则不变化
中间状态I (0=合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 阔达的项链(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 selfclass Success(State): def tran(self, ss, fsm): if ss.isupper(): return Fail(-2) return selfclass 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 selfclass 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（小于），您的支持是我不断更新的动力。