Algorithm
LeetCode算法题-10
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 preceding 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 = “cab” 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 = “misisp*.” Output: false
Java 程序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp;
int n = s.length();
int m = p.length();
// dp状态定义
dp = new boolean[n + 1][m + 1];
dp[n][m] = true;
// dp状态转移方程：从后往前
for (int i = n; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
boolean naiveMatch = i < n && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
if (j + 1 < m && p.charAt(j + 1) == '*') {
dp[i][j] = dp[i][j + 2] || naiveMatch && dp[i + 1][j];
} else {
dp[i][j] = naiveMatch && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}
Review
WTF is programmatic advertising?
- programmatic advertising, 是什么？程序化广告，计算广告
- RTB
- ad exchange，类似股票交易所，出价高者得之
- DMP
- SSP
- DSP
- viewability
Tip
- 技术债务要及时偿还，否则在未来的某一天会让你破产。对的事情，需要一贯坚持。
Share
- 这个假期完美的病倒了，身体健康每况愈下，引起重视
- 每个家庭成员的健康情况也牵动全家人的心，身体健康刻不容缓
