leetcode's People
leetcode's Issues
03. 无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
滑动窗口
左右指针, 初始指向0, result 为 0
- 检查右指针指向的字符是否存在(Map记录)
- 若不存在, len+1, 右指针+1
- 若存在,
- map中移除左指针目前指向的值, 左指针+1
- len-1, result更新为max(result, len)
- 最后输出 max(result, len)
var lengthOfLongestSubstring = function(s) {
const exist = new Map();
let left = 0, right = 0;
let result = 0
let len = 0;
while(right < s.length) {
const nextChar = s[right];
if(exist.has(nextChar)) {
exist.delete(s[left++])
result = Math.max(result, len--);
}else{
exist.set(nextChar, true);
len++;
right++;
}
}
return Math.max(result, len);
};
10. 正则表达式匹配
https://leetcode.cn/problems/regular-expression-matching/
动态规划
dp[i][j]
表示 p[0~j)
字串能否匹配s[0~i)
字串, 最终结果就是dp[s.length][p.length]
(注意, 这里采取左闭右开区间, 为了防止在j-2时数组越界)
状态转移公式需要根据p[j-1]的值分情况来看:
- 若
p[j-1]
是字母或'.', 则dp[i][j]
=>dp[i-1][j-1]
&& (s[i-1] === p[j-1] || p[j-1] === '.'
) - 若
p[j-1]
是'*':- 若p[j-2] === s[i-1]:
- 让'*'匹配零次,此时
dp[i][j]
=>dp[i][j-2]
- 让'*'匹配一次或多次,此时
dp[i][j]
=>dp[i-1][j]
- 让'*'匹配零次,此时
- 若
p[j-2]
!==s[i-1]
, 此时只能让'*'匹配零次dp[i][j]
=>dp[i][j-2]
- 若p[j-2] === s[i-1]:
var isMatch = function (s, p) {
const dp = new Array(s.length + 1);
for (let i = 0, l = dp.length; i < l; i += 1) {
dp[i] = new Array(p.length + 1).fill(false);
}
dp[0][0] = true;
for (let j = 1; j < p.length + 1; j++) {
if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
}
for (let i = 1, l = dp.length; i < l; i += 1) {
for (let j = 1, k = dp[i].length; j < k; j += 1) {
if (p[j - 1] === "." || p[j - 1] === s[i - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] === "*") {
if (p[j - 2] === s[i - 1] || p[j - 2] === ".") {
// 此时可以选择*匹配模式
// 若匹配0次, 直接扔掉, 那么i不变, j往前两位(扔掉*和前面匹配的那个字母)
// 若匹配1次, 则i往前一位, j不变, 在下一轮继续匹配
// 若匹配多次, 和匹配一次同理
dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
} else if (p[j - 2] !== s[i - 1]) {
// *前一位不匹配, 此时若还想继续匹配, 只能将*视为匹配0次
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[s.length][p.length];
};
console.log(isMatch("aab", "c*a*b"));
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.