1.开篇介绍
2.时间空间复杂度
3.动态规划
4.贪心
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.单调栈
14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其他类型题
dp[i][j]
表示子串i~j
是否是回文子串,循环s的子串,看是否满足s[i]
,s[j]
相等,如果相等,则dp[i][j]
是否为回文串取决于dp[i+1][j-1]
是否也是回文子串,在循环的过程中不断更新最大回文子串的长度,注意子串的长度是0或1也算回文子串O(n^2)
,两层循环。空间复杂度O(n^2)
,即动态规划dp数组的空间。Js:
var longestPalindrome = function(s) { let n = s.length; let res = ''; let dp = Array.from(new Array(n),() => new Array(n).fill(false));//初始化数组 for(let i = n-1;i >= 0;i--){//循环字符串 for(let j = i;j < n;j++){ //dp[i][j]表示子串i~j是否是回文子串 //回文子串必须满足s[i],s[j]相等。并且向外扩展一个字符也相等,即dp[i+1][j-1]也是回文子串 //j - i < 2表示子串小于等于1也是回文串 dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]); if(dp[i][j] && j - i +1 > res.length){//当前回文子串比之前的大,更新最大长度 res = s.substring(i,j+1); } } } return res; };
Java:
public String longestPalindrome(String s) { int N = s.length(); boolean[][] dp = new boolean[N][N]; String res = ""; for (int i = N - 1; i >= 0; i--) { for (int j = i; j < N; j++) { if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) { dp[i][j] = true; } if (dp[i][j] && (j - i + 1) > res.length()) { res = s.substring(i, j + 1); } } } return res; }
start+ maxLength
的子串就是本题的答案O(n^2)
,循环字符串一次,每次循环内部又向外不断扩张。空间复杂度O(1)
Js:
var longestPalindrome = function (s) { if (s.length <= 0) {//边界条件 return s; } let start = 0;//最长回文子串开始的索引 let maxLength = 1;//初始化最大回文子串长度 function h(left, right) { //当s[left],和 s[right]想等时,不断向外扩展回文字符串的长度 while (left >= 0 && right < s.length && s[left] === s[right]) { if (right - left + 1 > maxLength) { maxLength = right - left + 1;//更新最大回文子串的长度 start = left;//更新start的位置 } left--; right++; } } for (let i = 0; i < s.length; i++) { h(i - 1, i + 1);//回文子串是奇数 h(i, i + 1);//回文子串是偶数 } return s.substring(start, start + maxLength); };
Java:
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) { return ""; } //定义最长回文子串的长度 int maxLength = 1; //定义最长回文子串的起始位置 int start = 0; //遍历可能的回文子串的中心位置 for (int i = 0; i < s.length() - 1; i++) { //最长回文子串的长度为奇数时,中心位置为一个字符 int oddLength = expandAroundCenter(s, i, i); //最长回文子串的长度为偶数时,中心位置为两个字符 int evenLength = expandAroundCenter(s, i, i + 1); int length = Math.max(oddLength, evenLength); //找出最大长度 if (maxLength < length) { maxLength = length; //计算start位置 start = i - (maxLength - 1) / 2; } } //截取字符串 return s.substring(start, start + maxLength); } //返回最长回文子串的长度 public int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length()) { if (s.charAt(left) == s.charAt(right)) { //边界向外扩展 left--; right++; } else { break; } } //最后一次向外扩展不满足条件,还原该次扩展 left++; right--; return right - left + 1; } }
O(n)
,空间复杂度O(1)
。例子:
输入: s = "aba" 输出: true 输入: s = "abca" 输出: true 解释: 你可以删除c字符。
js:
function isPalindrome(str, l, r) { while (l < r) { //对撞指针不断判断两边的数字是否相等 if (str[l] != str[r]) { return false; } l++; r--; } return true; } var validPalindrome = function (str) { let l = 0, r = str.length - 1; //头尾指针 while (l < r) { if (str[l] != str[r]) {//左右指针不一样 还有一次机会,左指针向前一步或者右指针向后一步继续验证 return isPalindrome(str, l + 1, r) || isPalindrome(str, l, r - 1); } l++; r--; } return true; };
java:
class Solution { public boolean validPalindrome(String s) { int l = 0, r = s.length() - 1; while (l < r) { char c1 = s.charAt(l), c2 = s.charAt(r); if (c1 == c2) { ++l; --r; } else { return validPalindrome(s, l, r - 1) || validPalindrome(s, l + 1, r); } } return true; } public boolean validPalindrome(String s, int l, int r) { for (int i = l, j = r; i < j; ++i, --j) { char c1 = s.charAt(i), c2 = s.charAt(j); if (c1 != c2) { return false; } } return true; } }
dp[i]
表示以i结尾的最长有效括号的长度,分为4种情况,看图O(n)
,n是字符串的长度,总共遍历1次。空间复杂度O(n)
,即dp数组的空间js:
const longestValidParentheses = (s) => { let maxLen = 0; const len = s.length; const dp = new Array(len).fill(0); for (let i = 1; i < len; i++) { if (s[i] == ')') {//以')'结尾的字符才有效 if (s[i - 1] == '(') {//如果前一个位置是'(' 则能与当前字符形成有效括号 if (i - 2 >= 0) {//如果前2个位置还有字符串 dp[i] = dp[i - 2] + 2;//当前状态等于 当前匹配的2个字符 加上 前两个位置匹配最长字符长度 } else {//如果前2个位置没有字符串 dp[i] = 2;//当前状态等于 当前匹配的2个字符 } //以i-1结尾的有效字符在向前看1个位置 如果是'(' 则能与当前字符形成有效括号 } else if (s[i - dp[i - 1] - 1] == '(') { if (i - dp[i - 1] - 2 >= 0) {//以i-1结尾的有效字符在向前看2个位置 如果>=于0 //当前状态=以i-1结尾的有效字符长度 + 当前匹配2个有效括号 + 以i - dp[i - 1] - 2结尾的有效字符长度 dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]; } else { //以i-1结尾的有效字符在向前看2个位置 如果<于0 //当前状态=以i-1结尾的有效字符长度 + 当前匹配2个有效括号 dp[i] = dp[i - 1] + 2; } } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; };
Java:
class Solution { public int longestValidParentheses(String s) { int maxLen = 0; int[] dp = new int[s.length()]; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; } maxLen = Math.max(maxLen, dp[i]); } } return maxLen; } }
O(n)
,n是字符串的长度,总共遍历1次。空间复杂度O(n)
,即栈的空间动画过大,点击查看
js:
var longestValidParentheses = function (s) { let maxLen = 0 let stack = [] stack.push(-1) // 初始化一个参照物 for (let i = 0; i < s.length; i++) { if (s[i] === '(') { // ( 入栈 )出栈 stack.push(i) } else { // )的情况 出栈 stack.pop() if (stack.length) { // 每次出栈 计算下当前有效连续长度 // 如何计算连续长度 当前位置 - 栈顶下标 maxLen = Math.maxLen(maxLen, i - stack[stack.length - 1]) } else { stack.push(i) //栈为空时 放入右括号参照物 表示从这个下标开始 需要重新计算长度 } } } return maxLen };
java:
class Solution { public int longestValidParentheses(String s) { int maxLen = 0; Deque<Integer> stack = new LinkedList<Integer>(); stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); } else { maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; } }
left++
,遇见')' , right++
,当左右括号数量相同时,更新最大长度,如果right大于left,则重置left、right 重新计数O(n)
,n是字符串的长度,总共遍历2次。空间复杂度O(1)
Js:
var longestValidParentheses = function (s) { let maxLen = 0; let left = 0; let right = 0; for (let i = 0; i < s.length; i++) {//从左往右 if (s[i] == "(") { //遇见'(' left++ left++; } else { right++; //遇见')' right++ } if (left == right) { //左右数量相同 maxLen = Math.max(maxLen, 2 * left); //更新最大长度 } else if (right > left) { //right大于left 重置left right 重新计数 left = right = 0; } } left = right = 0; for (let i = s.length - 1; i >= 0; i--) { //从右往左 if (s[i] == "(") { left++; } else { right++; } if (left == right) { maxLen = Math.max(maxLen, right * 2); } else if (left > right) { left = right = 0; } } return maxLen; };
Java:
class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, maxLen = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxLen = Math.max(maxLen, 2 * right); } else if (right > left) { left = right = 0; } } left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxLen = Math.max(maxLen, 2 * left); } else if (left > right) { left = right = 0; } } return maxLen; } }
js:
var removeInvalidParentheses = function (s) { let res = []; let queue = []; let visited = new Set();//去重 queue.push(s); while (true) { let size = queue.length;//[s] for (let i = 0; i < size; i++) { s = queue.shift();//出队 if (isVaild(s)) {//如果是合法字符串 res.push(s);//加入结果数组 } else if (res.length == 0) {//不合法并且res.length == 0 则进入bfs下一层 尝试删除字符 for (let i = 0; i < s.length; i++) { if (s[i] == '(' || s[i] === ')') {//是左右括号尝试删除字符,否则跳过 let nexts = s.substring(0, i) + s.substring(i + 1); if (!visited.has(nexts)) {//判断新生成的字符串是否重复 queue.push(nexts);//加入队列 进入下一层 [s1,s2...] visited.add(nexts);//加入去重数组 } } } } } if (res.length > 0) {//出现合法字符串的那一层,终止循环 break; } } return res; }; function isVaild(s) { let count = 0; for (let i = 0; i < s.length; i++) { if (s[i] === '(') {//左括号count+1 count++; } else if (s[i] === ')') {//右括号count-1 count--; } if (count < 0) {//小于0 说明右括号多 return false; } } return count === 0; }
java:
public class Solution { public List<String> removeInvalidParentheses(String s) { List<String> res = new ArrayList<>(); if (s == null) { return res; } Set<String> visited = new HashSet<>(); visited.add(s); Queue<String> queue = new LinkedList<>(); queue.add(s); boolean found = false; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String front = queue.poll(); if (isValid(front)) { res.add(front); found = true; } int currentWordLen = front.length(); char[] charArray = front.toCharArray(); for (int j = 0; j < currentWordLen; j++) { if (front.charAt(j) != '(' && front.charAt(j) != ')') { continue; } String next = new String(charArray, 0, j) + new String(charArray, j + 1, currentWordLen - j - 1); if (!visited.contains(next)) { queue.offer(next); visited.add(next); } } } if (found) { break; } } return res; } public boolean isValid(String s) { char[] charArray = s.toCharArray(); int count = 0; for (char c : charArray) { if (c == '(') { count++; } else if (c == ')') { count--; } if (count < 0) { return false; } } return count == 0; } }
O(n)
,空间复杂度O(k)
,k是字符集大小js:
var firstUniqChar = function (s) { const counts = new Array(26).fill(0); //长度为26的数组,存放字符的出现次数 for (const c of s) { //遍历s,统计每个字符出现次数 counts[c.charCodeAt(0) - 97]++; //97是a的Unicode值 } for (let i = 0; i < s.length; i++) { //再次遍历s if (counts[s[i].charCodeAt(0) - 97] == 1) {//找出第一个频次为1的字符的索引 return i; } } return -1; };
java:
class Solution { public int firstUniqChar(String s) { Map<Character, Integer> frequency = new HashMap<Character, Integer>(); for (int i = 0; i < s.length(); ++i) { char ch = s.charAt(i); frequency.put(ch, frequency.getOrDefault(ch, 0) + 1); } for (int i = 0; i < s.length(); ++i) { if (frequency.get(s.charAt(i)) == 1) { return i; } } return -1; } }
O(n)
,空间复杂度O(k)
,k是字符集大小js:
var firstUniqChar = function(s) { const position = new Map(); const q = []; for (let [i, ch] of Array.from(s).entries()) { //循环字符串s,如果map中未出现当前字符,则将字符串和位置索引加入map和队列中 if (!position.has(ch)) { position.set(ch, i); q.push([ch, i]); } else { position.set(ch, -1);//当出现重复字符时 map中的字符对应的value设置成-1 //如果队头元素对应在map中的value是-1,说明是重复元素,不断出队,直到队头是不重复的元素 while (q.length && position.get(q[0][0]) === -1) { q.shift(); } } } return q.length ? q[0][1] : -1;//如果队列中存在元素,队头就是第一个不重复的字符 };
java:
class Solution { public int firstUniqChar(String s) { Map<Character, Integer> position = new HashMap<Character, Integer>(); Queue<Pair> queue = new LinkedList<Pair>(); int n = s.length(); for (int i = 0; i < n; ++i) { char ch = s.charAt(i); if (!position.containsKey(ch)) { position.put(ch, i); queue.offer(new Pair(ch, i)); } else { position.put(ch, -1); while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) { queue.poll(); } } } return queue.isEmpty() ? -1 : queue.poll().pos; } class Pair { char ch; int pos; Pair(char ch, int pos) { this.ch = ch; this.pos = pos; } } }
O(mn)
,m是字符串最长长度,n是字符数组长度f l o w e r f l o w f l i g h t
js:
var longestCommonPrefix = function(strs) { if(strs.length == 0) return ""; let ans = strs[0];//ans初始值为字符串数组的第一个 for(let i =1;i<strs.length;i++) {//循环字符串数组 let j=0; for(;j<ans.length && j < strs[i].length;j++) {//循环字符,找到第一个不相同的位置 if(ans[j] != strs[i][j]) break; } ans = ans.substr(0, j);//从0号位置到第一个不相同的位置 截取字符串 if(ans === "") return ans; } return ans; };
java:
class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0) return ""; String ans = strs[0]; for(int i =1;i<strs.length;i++) { int j=0; for(;j<ans.length() && j < strs[i].length();j++) { if(ans.charAt(j) != strs[i].charAt(j)) break; } ans = ans.substring(0, j); if(ans.equals("")) return ans; } return ans; } }
O(n)
。空间复杂度O(1)
js:
var reverseString = function(s) { const n = s.length; //双指针不断交换left和right位置的元素 for (let left = 0, right = n - 1; left < right; left++, right--) { [s[left], s[right]] = [s[right], s[left]]; } };
java:
class Solution { public void reverseString(char[] s) { int n = s.length; for (int left = 0, right = n - 1; left < right; left++, right--) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; } } }
js:
var reverseWords = function(s) { return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ') };
java:
class Solution { public String reverseWords(String s) { s = s.trim(); List<String> wordList = Arrays.asList(s.split("\\s+")); Collections.reverse(wordList); return String.join(" ", wordList); } }
s.length - 1
位置,遍历字符串,将每个由空格分隔的字符串加入队列,最后在转回字符串就是翻转过后的了O(n)
,空间复杂度O(n)
js:
//"the sky is blue" var reverseWords = function(s) { let left = 0 let right = s.length - 1 let queue = [] let word = '' //去掉左右的空格 while (s.charAt(left) === ' ') left ++ while (s.charAt(right) === ' ') right -- while (left <= right) { let char = s.charAt(left) if (char === ' ' && word) { queue.unshift(word)//字符串加入队列 word = ''//重置字符串 } else if (char !== ' '){//拼接单个字符串 word += char } left++ } queue.unshift(word)//最后一个字符串也要加入队列 return queue.join(' ')//转回字符串 };
java:
class Solution { public String reverseWords(String s) { int left = 0, right = s.length() - 1; while (left <= right && s.charAt(left) == ' ') { ++left; } while (left <= right && s.charAt(right) == ' ') { --right; } Deque<String> d = new ArrayDeque<String>(); StringBuilder word = new StringBuilder(); while (left <= right) { char c = s.charAt(left); if ((word.length() != 0) && (c == ' ')) { d.offerFirst(word.toString()); word.setLength(0); } else if (c != ' ') { word.append(c); } ++left; } d.offerFirst(word.toString()); return String.join(" ", d); } }
思路:注意子序列可以不连续
状态定义:dp[i][j]
表示 text1[0:i-1]
和 text2[0:j-1]
的最长公共子序列,注意是闭区间,之所以是到i-1
或j-1
,是方便初始化dp数组,当i=0
或者j=0
的时候表示的就是空字符和另一个字符串匹配,此时的dp[i][j]=0
状态转移方程:当text1[i - 1] == text2[j - 1]
时:dp[i][j] = dp[i - 1][j - 1] + 1
当text1[i - 1] != text2[j - 1]
时:dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
;
dp的初始化:当 i = 0 时:dp[0][j]=0
当 j = 0
时:dp[i][0]=0
返回结果:dp[len(text1)][len(text2)]
复杂度:时间复杂度O(mn)
,空间复杂度O(mn)
js:
var longestCommonSubsequence = function(text1, text2) { const m = text1.length, n = text2.length; const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));//初始化dp for (let i = 1; i <= m; i++) { const c1 = text1[i - 1]; for (let j = 1; j <= n; j++) { const c2 = text2[j - 1]; if (c1 === c2) { dp[i][j] = dp[i - 1][j - 1] + 1;//text1与text2字符相同时 最长公共子序列长度+1 } else { //text1与text2字符不同时 返回text1或text2向前减少一位之后的最长公共子序列中的较大者 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; };
java:
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { char c1 = text1.charAt(i - 1); for (int j = 1; j <= n; j++) { char c2 = text2.charAt(j - 1); if (c1 == c2) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }
思路:拆分成不同子串的匹配,这些匹配存在重复子结构,可以用动态规划来做
状态定义:dp[i][j]
表示以i-1为结尾的s,它的子序列中出现以j-1为结尾的t的个数为dp[i][j]
状态转移方程:
s[i-1] == t[j-1]
时:
1.用s[i - 1]
来匹配,dp[i][j] = dp[i - 1][j - 1]
,
2.不用s[i - 1]
来匹配,dp[i][j] = dp[i-1][j]
。
s[i-1] != t[j-1]
时:就不能用s[i - 1]
来匹配,dp[i][j] = dp[i-1][j]
初始状态:
dp[i][0] =1
:当j=0
时,相当于t是空字符串,空字符在另一个字符串的子串中出现一次,此时第一列都初始化为1。dp[i][j] =0
复杂度:时间复杂度O(mn)
,m,n分别是s和t的长度。空间复杂度O(mn)
,dp数组的空间
js:
//dp[i][j]表示以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j] const numDistinct = (s, t) => { //初始化dp数组, let dp = Array.from(Array(s.length + 1), () => Array(t.length +1).fill(0)); //当j=0时,相当于t是空字符串,空字符在另一个字符串的子串中出现一次,此时第一列都初始化为1, for(let i = 0; i <=s.length; i++) { dp[i][0] = 1; } //当s[i-1] == t[j-1]: //1.用s[i - 1]来匹配 dp[i][j] = dp[i-1][j-1] //2.不用s[i - 1]来匹配 dp[i][j] = dp[i-1][j] //当s[i-1] != t[j-1]:不能用s[i-1]来匹配,s[i - 1]匹配不了t[j-1],所以dp[i][j] = dp[i-1][j] for(let i = 1; i <= s.length; i++) { for(let j = 1; j<= t.length; j++) { if(s[i-1] === t[j-1]) { dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } else { dp[i][j] = dp[i-1][j] } } } return dp[s.length][t.length]; };
java:
class Solution { public int numDistinct(String s, String t) { int[][] dp = new int[s.length() + 1][t.length() + 1]; for (int i = 0; i < s.length() + 1; i++) { dp[i][0] = 1; } for (int i = 1; i < s.length() + 1; i++) { for (int j = 1; j < t.length() + 1; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; }else{ dp[i][j] = dp[i - 1][j]; } } } return dp[s.length()][t.length()]; } }
思路:用正则去掉无关字符,然后对撞指针判断左右两边是否是相同的字符
复杂度:时间复杂度O(n)
,空间复杂度O(1)
js:
var isPalindrome = function (s) { s = s.replace(/[\W|_]/g, "").toLowerCase(); if (s.length < 2) { return true; } let left = 0; let right = s.length - 1; while (left < right) { if (s[left] !== s[right]) {//对撞指针判断左右两边是否是相同的字符 return false; } left++; right--; } return true; };
java:
public boolean isPalindrome(String s) { String lowerCase = s.toLowerCase(); int left = 0; int right = lowerCase.length() - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(left))) { left++; } while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(right))) { right--; } if (lowerCase.charAt(left) != lowerCase.charAt(right)) { return false; } left++; right--; } return true; }
O(n^2)
,比较一个字符串是否包含另一个字符串的复杂度O(n^2)
。空间复杂度O(n)
js
var rotateString = function (A, B) { return A.length <= B.length && (A + A).includes(B) };
java:
class Solution { public boolean rotateString(String A, String B) { return A.length() == B.length() && (A + A).contains(B); } }
方法1.截取字符串,循环字符串,遇到#就截掉最后一个字符,循环完毕之后,最后比较两个去除掉#退格之后的字符串是否相等,时间复杂度O(m+n)
,m、n是两个字符串的长度。空间复杂度O(1)
方法2.双指针
O(m+n)
,m、n是两个字符串的长度。空间复杂度O(1)
js:
var backspaceCompare = function(S, T) { let i = S.length - 1, j = T.length - 1, skipS = 0, skipT = 0; //双指针从右往左循环 while(i >= 0 || j >= 0){ while(i >= 0){//处理掉# 直到left指向的字符右边退格全部处理掉 if(S[i] === '#'){ skipS++; i--; }else if(skipS > 0){ skipS--; i--; }else break; } while(j >= 0){//处理掉# 直到right指向的字符右边退格全部处理掉 if(T[j] === '#'){ skipT++; j--; }else if(skipT > 0){ skipT--; j--; }else break; } if(S[i] !== T[j]) return false;//如果处理掉退格之后的字符串不相等,返回false i--;//继续循环 j--; } return true;//如果循环过程中没返回false 最后就返回true };
java:
class Solution { public boolean backspaceCompare(String S, String T) { int i = S.length() - 1, j = T.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { while (i >= 0) { if (S.charAt(i) == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } } while (j >= 0) { if (T.charAt(j) == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } if (i >= 0 && j >= 0) { if (S.charAt(i) != T.charAt(j)) { return false; } } else { if (i >= 0 || j >= 0) { return false; } } i--; j--; } return true; } }
// "Let's take LeetCode contest" const reverseWords = s => { const arr = s.split(' '); const res = []; for (let i = 0; i < arr.length; i++) { res.push(arr[i].split('').reverse().join('')); } return res.join(' '); };
js:
// "Let's take LeetCode contest" var reverseWords = function (s) { let arr = s.split(""); let l = 0, r = l; while (l < arr.length) { //找到结尾的空格 while (arr[r] && arr[r] !== " ") { r++; } //反转单词 for (let i = l, j = r - 1; i < j; i++, j--) { [arr[i], arr[j]] = [arr[j], arr[i]]; } //跳到下一个单词 l = r + 1; r = l; } return arr.join(""); };