第五周

Alogrithm

题目—Longest Palindromic Substring

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:

    s could be empty and contains only lowercase letters a-z.
    p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:

    Input:
    s = "aa"
    p = "a"
    Output: false
    Explanation: "a" does not match the entire string "aa".
Example 2:

    Input:
    s = "aa"
    p = "a*"
    Output: true
    Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:

    Input:
    s = "ab"
    p = ".*"
    Output: true
    Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:

    Input:
    s = "aab"
    p = "c*a*b"
    Output: true
    Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:

    Input:
    s = "mississippi"
    p = "mis*is*p*."
    Output: false"

又一个Hard难度的题目，同时又是一个DP的题目。所以借着这个题目这周刷Introduction to Agorithms详细学了一下DP相关的知识。

DP相关内容记录：

DP中programming指的是一种表格法，而非计算机程序的“programming”
可以应用DP的最优化问题的两个要素：最优子结构和子问题重叠
最优子结构——用子问题最优解来构造原问题的最优解（贪心算法也有这个条件）
重叠子问题——子问题空间应该尽量小，方便通过记录的子问题最优解减少运算量（分治方法每一步都是新的子问题）
需要有一个备忘机制记录子问题结果（可以是本题中类似的多维数组记录，后续结果由前面结果组合产生）

中途遇到了两个坑

a*开头的pattern输入的处理
这种情况需要预处理，因为只要是这种可以为0次重复的状态，和空输入的对比也应当返回ture。
子问题迭代方式没想清楚
1
2
"aaa"
"ab*a*c*a"

这个用例通不过的问题，主要还是当aa和ab*a*这种情况下，如果只取dp[i][j] = dp[i-1][j](即只在s侧减少一个字符来对比)，则会把aa直接消掉，导致空与ab*a*比较的情况而错误判定为不符合。所以*前字符和s符合情况下，应该为dp[i][j] = dp[i-1][j] || dp[i][j - 2]。

答案：

unsigned long slen = s.size(), plen = p.size();
std::vector<std::vector<bool>>
    dp(slen + 1, std::vector<bool> (plen + 1, false));
dp[0][0] = true;
// init for s = '' and p = 'a*'
for (int k = 1; k < plen + 1; ++k) {
  if (p[k - 1] == '*') dp[0][k] = dp[0][k - 2];
}
for (int i = 1; i < slen + 1; ++i) {
  for (int j = 0; j < plen + 1; ++j) {
    if (j == 0) {
      dp[i][j] = false;
      continue;
    }
    if (s[i - 1] == p[j - 1] || p[j - 1] == '.') dp[i][j] = dp[i - 1][j - 1];
    else if (p[j - 1] == '*') {
      if (s[i - 1] == p[j - 2] || p[j - 2] == '.') dp[i][j] = dp[i-1][j] || dp[i][j - 2];
      else dp[i][j] = dp[i][j-2];
    }
  }
}
return dp[slen][plen];

Coding Tips:

C++中数组是无法使用非常量声明的，可以考虑使用Vector代替。二维的Vector可以这样声明：vector<vector<bool>> dp(m, vector<bool> (n, false))
注意区分for循环中的break和continue，前者是直接跳出for循环，后者是进入下一个循环

Reading

Follow these steps to solve any Dynamic Programming interview problem

这篇文章归纳了解决动态规划问题的7个步骤：

分辨一个动态规划问题
DP的核心在于通过把一个问题拆分成若干个更简单的小问题解决，并将每个小问题的结果存储下来，以节省后续运算次数。（少量空间换大量时间）
确定变量
关键在于确定变量有几个，以确定整个子问题结果需要存储空间的维度
清晰表达可重复问题之间的关系
如同中学的数学归纳法，描述如何层层迭代，最终求得主问题
找到基础情况
找到不依赖于其他子问题的基础问题
确定使用循环还是递归
添加备忘机制
确定时间复杂度
通过确定状态数以及计算每个状态需要的运算量确定时间复杂度

Tips

Clion 2018.3版本之后总算支持一键在服务器侧的远程调试了：Full Remote Mode

最近看到同事对合作商的筛选中引用了Gartner的报告和排名，包括对各公司的市场划分。遂到Gartner上搜索了下相关报告，发现除了报告价格，一切都很好。
其中Gartner对市场中公司排名与角色划分的Magic Quadrant还是很有用的。

P.S. Niche Player（利基者）是指专注在某特定细分领域的市场参与者

Alogrithm

题目—Longest Palindromic Substring

Reading

Tips

Share