xfeif / leetcode Goto Github PK

Description

题意

判断字符串匹配。给定输入string s, 和一个pattern p，判断p是否能匹配整个s。
这里有两个需要注意的字符：

• .可以匹配任意单个字符；
• *可以表示它前面的字符重复0次或者多次。
  因此.*可以表示任意长度的串。

分析

多样例分析

1. p = a.b
   s = acb, aab, axb -> True : .匹配任意单个字符，匹配且只匹配一个。
   s = ab, acby, cb -> False ：acby多了y, cb中a不匹配。
2. p = a*b
   s = b, ab, aab, aaab ->True: *表示a重复0次或多次。
   s = a, acb -> False: b至少出现一次，a*不能表示ac。
3. p = a*b.*y
   s = by, bly, ably, ablmy -> True: a*表示a重复0次或多次，.*表示b,y之间可以有任意字符串
   s = ay, ab -> False: 缺少b或y

类型分析

首先我们确定一下这是哪种题型。

我们通过上面的样例进一步分析，一般我们设两个指针，分别用来标记字符串和pattern的位置，对应位置字符相同，我们就比较下一个，出现特殊字符的时候，需要进一步考虑。直到最后比完。

我们知道，如果s[i+1]和p[j+1]能够匹配上，那么从开头到i+1是否能够完全匹配上，取决于s[0...i]和p[0...j]匹配的结果，并且当前比较是不受前面比较的影响。于是我们可以将两个完整串的匹配分解成一个个独立的子问题来解。

再想想动态规划的两个性质（最优子结构，重叠子问题），不难想到这题属于动态规划（DP）问题。那么我们就针对DP问题的解法来思考。

解析

在判断出本题属于DP问题后，我们需要以下三步走：

1. 定义状态
2. 寻找状态转移方程
3. 制表或者记忆化求解

状态

根据上面的分析，我们可以使用s[0...i]和p[0...j]的匹配状态作为整体的状态，那么我们需要一个二维的状态矩阵dp，纬度分别为len(s)+1，len(p)+1。

状态转移方程

首先初始化dp，若s,p均为空串则dp[0][0]=True，若二者只有一个为空串，那么均匹配失败。

if s[i] == p[j] or p[j] == '.', dp[i][j] = dp[i-1][j-1];

elif p[j] == '*'，这个时候要分两种情况考虑。一是*前的字母出现0次，那么当前状态应取决于，当前字符位和匹配串前两位之前的匹配状态，即dp[i][j] = dp[i][j-2]。另一种情况，考虑前面的字符出现了一次或多次，即将s[i]与p[j-1]比较，或者匹配串前一个字符p[j-1]为.，这种情况下，dp[i][j] = dp[i-1][j] ，综合考虑起来，就是取二者的或。

Code

留给自己二刷补充。

Description

Description

1106. Parsing A Boolean Expression

总结：直觉的数学思路（化简） + 一些 python 语言细节。

1WA，2TLE 以及参考了其他人的做法才解出来。

首先简单的地方在于最简单的基本情况只有一个字符，很好判断。

复杂的地方在于表达式嵌套，想找到一种方法解嵌套。

自己举几个例子可以发现，每一个基本情况都需要计算。也就是与或非三个基本表达式，那么问题转化为将每个基本情况都计算出来，然后进行化简。

再深入一层，需要找到每个基本情况。

我最开始尝试采用递归的方法，肯定可以做出来。但是我没有，我在处理一些特殊情况的时候，考虑不全面以及写的很复杂，相当于是每种特殊情况我都要列出来……

打开讨论界面，标题里出现次数比较多的关键词是stack。

考虑一下，用栈的方式的话，读取表达式，每次都可以先处理一个基本情况，将基本情况转化为t或者f，这样一直把复杂表达式中子表达式化简成最简形式，最后得到的表达式也就是最简形式了。

What Today

Todos

• what
• yes
• no
• test
• ttt

Description