大廠算法面試之leetcode精講20.字符串
視頻講解（高效學習）:點擊學習
目錄：
5. 最長回文子串 （medium）
方法1.動態(tài)規(guī)劃
ds_100
- 思路：定義
dp[i][j]表示子串i～j是否是回文子串是己，循環(huán)s的子串椿争，看是否滿足s[i]市栗，s[j]相等，如果相等诸衔，則dp[i][j]是否為回文串取決于dp[i+1][j-1]是否也是回文子串，在循環(huán)的過程中不斷更新最大回文子串的長度隘击，注意子串的長度是0或1也算回文子串 - 復雜度：時間復雜度
O(n^2)替久，兩層循環(huán)”枭耄空間復雜度O(n^2)清钥，即動態(tài)規(guī)劃dp數(shù)組的空間。
Js:
var longestPalindrome = function(s) {
let n = s.length;
let res = '';
let dp = Array.from(new Array(n),() => new Array(n).fill(false));//初始化數(shù)組
for(let i = n-1;i >= 0;i--){//循環(huán)字符串
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;
}
方法2.中心擴散法
ds_99
- 思路：分最長回文子串是奇數(shù)和偶數(shù)的情況篡悟，定義start為最長回文子串開始的索引，然后循環(huán)字符串础钠，不斷不斷向外擴展回文字符串的長度恰力，循環(huán)的過程中更新最大回文子串的長度和start的位置，最后返回start到
start+ maxLength的子串就是本題的答案 - 復雜度：時間復雜度
O(n^2)旗吁，循環(huán)字符串一次踩萎，每次循環(huán)內(nèi)部又向外不斷擴張『艿觯空間復雜度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);//回文子串是奇數(shù)
h(i, i + 1);//回文子串是偶數(shù)
}
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++) {
//最長回文子串的長度為奇數(shù)時，中心位置為一個字符
int oddLength = expandAroundCenter(s, i, i);
//最長回文子串的長度為偶數(shù)時企孩，中心位置為兩個字符
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;
}
}
680. 驗證回文字符串 Ⅱ （easy）
- 思路：對撞指針不斷判斷左右兩邊的數(shù)字是否相等 ，如果不相等還有一次機會勿璃，左指針向前一步或者右指針向后一步繼續(xù)驗證
- 復雜度：時間復雜度
O(n)擒抛，空間復雜度O(1)。
例子：
輸入: s = "aba"
輸出: true
輸入: s = "abca"
輸出: true
解釋: 你可以刪除c字符补疑。
js：
function isPalindrome(str, l, r) {
while (l < r) { //對撞指針不斷判斷兩邊的數(shù)字是否相等
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]) {//左右指針不一樣 還有一次機會歧沪，左指針向前一步或者右指針向后一步繼續(xù)驗證
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;
}
}
32. 最長有效括號 （hard）
方法1.動態(tài)規(guī)劃
- 思路：
dp[i]表示以i結(jié)尾的最長有效括號的長度，分為4種情況莲组，看圖 - 復雜度：時間復雜度
O(n)诊胞，n是字符串的長度，總共遍歷1次锹杈∧旃拢空間復雜度O(n)，即dp數(shù)組的空間
ds_10
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] == ')') {//以')'結(jié)尾的字符才有效
if (s[i - 1] == '(') {//如果前一個位置是'(' 則能與當前字符形成有效括號
if (i - 2 >= 0) {//如果前2個位置還有字符串
dp[i] = dp[i - 2] + 2;//當前狀態(tài)等于 當前匹配的2個字符 加上 前兩個位置匹配最長字符長度
} else {//如果前2個位置沒有字符串
dp[i] = 2;//當前狀態(tài)等于 當前匹配的2個字符
}
//以i-1結(jié)尾的有效字符在向前看1個位置 如果是'(' 則能與當前字符形成有效括號
} else if (s[i - dp[i - 1] - 1] == '(') {
if (i - dp[i - 1] - 2 >= 0) {//以i-1結(jié)尾的有效字符在向前看2個位置 如果>=于0
//當前狀態(tài)=以i-1結(jié)尾的有效字符長度 + 當前匹配2個有效括號 + 以i - dp[i - 1] - 2結(jié)尾的有效字符長度
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
} else {
//以i-1結(jié)尾的有效字符在向前看2個位置 如果<于0
//當前狀態(tài)=以i-1結(jié)尾的有效字符長度 + 當前匹配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;
}
}
方法2.棧
- 思路：遍歷字符串竭望，準備一個棧邪码，存放字符串下標，首先放入初始參照物-1市框，遇到'('入棧霞扬，遇到')'出棧，并且判斷棧長度枫振，如果不為空喻圃，更新最大合法字符串長度，否則將當前下標放入棧中
- 復雜度：時間復雜度
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) {
// 每次出棧 計算下當前有效連續(xù)長度
// 如何計算連續(xù)長度 當前位置 - 棧頂下標
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;
}
}
方法3.兩次遍歷
- 思路：從左到右予权，從右到左依次遍歷字符串昂勉，遇見'(' ,
left++，遇見')' ,right++扫腺，當左右括號數(shù)量相同時岗照，更新最大長度，如果right大于left，則重置left攒至、right 重新計數(shù) - 復雜度：時間復雜度
O(n)厚者，n是字符串的長度，總共遍歷2次迫吐】夥疲空間復雜度O(1)
ds_12
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) { //左右數(shù)量相同
maxLen = Math.max(maxLen, 2 * left); //更新最大長度
} else if (right > left) { //right大于left 重置left right 重新計數(shù)
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;
}
}
301. 刪除無效的括號 （hard）
方法1:bfs
ds_111
- 思路：最少刪除的括號數(shù)量，這種求最短或者最少的題目志膀，聯(lián)想到bfs熙宇，bfs第一個出現(xiàn)解的層，即為最短刪除括號所形成的合法字符串溉浙。準備queue對字符串進行bfs搜索奇颠，出現(xiàn)合法字符串入隊，否則嘗試刪除一個字符放航，進入下一層判斷，注意合法字符可能重復圆裕，需要去重广鳍。
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);//加入結(jié)果數(shù)組
} 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);//加入去重數(shù)組
}
}
}
}
}
if (res.length > 0) {//出現(xiàn)合法字符串的那一層吓妆，終止循環(huán)
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;
}
}
387. 字符串中的第一個唯一字符 （easy）
方法1:哈希表
- 思路：統(tǒng)計字符出現(xiàn)的頻次赊时，找出第一個頻次為1的字符的索引
- 復雜度：時間復雜度
O(n)鹰祸，空間復雜度O(k)油够，k是字符集大小
js：
var firstUniqChar = function (s) {
const counts = new Array(26).fill(0); //長度為26的數(shù)組抚垄，存放字符的出現(xiàn)次數(shù)
for (const c of s) { //遍歷s实愚，統(tǒng)計每個字符出現(xiàn)次數(shù)
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;
}
}
方法2:隊列
- 思路：循環(huán)字符串s歹鱼，如果map中未出現(xiàn)當前字符输枯，則將字符串和位置索引加入map和隊列中精耐，當出現(xiàn)重復字符時傻粘，map中的字符對應(yīng)的value設(shè)置成-1沼瘫，如果隊頭元素對應(yīng)在map中的value是-1抬纸，說明是重復元素，不斷出隊耿戚，直到隊頭是不重復的元素湿故。循環(huán)結(jié)束之后，如果隊列中存在元素膜蛔，隊頭就是第一個不重復的字符
- 復雜度：時間復雜度
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()) {
//循環(huán)字符串s皂股，如果map中未出現(xiàn)當前字符墅茉，則將字符串和位置索引加入map和隊列中
if (!position.has(ch)) {
position.set(ch, i);
q.push([ch, i]);
} else {
position.set(ch, -1);//當出現(xiàn)重復字符時 map中的字符對應(yīng)的value設(shè)置成-1
//如果隊頭元素對應(yīng)在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;
}
}
}
14. 最長公共前綴 （easy）
- 思路：縱向掃描字符串，找到第一個不相同的位置
- 復雜度：時間復雜度
O(mn)战转，m是字符串最長長度搜立，n是字符數(shù)組長度
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初始值為字符串數(shù)組的第一個
for(let i =1;i<strs.length;i++) {//循環(huán)字符串數(shù)組
let j=0;
for(;j<ans.length && j < strs[i].length;j++) {//循環(huán)字符，找到第一個不相同的位置
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;
}
}
344. 反轉(zhuǎn)字符串 （easy）
- 思路：指針left初始時指向0號位置槐秧，right初始指向n-1的位置啄踊。雙指針不斷交換left和right位置的元素
- 復雜度：時間復雜度
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;
}
}
}
151. 翻轉(zhuǎn)字符串里的單詞 (medium)
方法1:正則
- 思路：將字符串頭尾空格去掉颠通，然后將那個多個空格用正則替換成一個空格，根據(jù)空格分隔成數(shù)組膀懈，然后翻轉(zhuǎn)轉(zhuǎn)回字符串
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);
}
}
方法2:雙端隊列
- 思路：left指針初始在0號位置顿锰，right指針初始在
s.length - 1位置，遍歷字符串启搂，將每個由空格分隔的字符串加入隊列硼控，最后在轉(zhuǎn)回字符串就是翻轉(zhuǎn)過后的了 - 復雜度：時間復雜度
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(' ')//轉(zhuǎn)回字符串
};
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);
}
}
1143. 最長公共子序列 (medium)
方法1:動態(tài)規(guī)劃
ds_151
ds_152
-
思路：注意子序列可以不連續(xù)
狀態(tài)定義：
dp[i][j]表示text1[0:i-1]和text2[0:j-1]的最長公共子序列胳赌，注意是閉區(qū)間牢撼，之所以是到i-1或j-1，是方便初始化dp數(shù)組疑苫，當i=0或者j=0的時候表示的就是空字符和另一個字符串匹配熏版，此時的dp[i][j]=0-
狀態(tài)轉(zhuǎn)移方程：當
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 返回結(jié)果：
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];
}
}
115. 不同的子序列 (hard)
方法1.動態(tài)規(guī)劃
ds_153
ds_154
-
思路：拆分成不同子串的匹配捍掺，這些匹配存在重復子結(jié)構(gòu)撼短，可以用動態(tài)規(guī)劃來做
狀態(tài)定義：
dp[i][j]表示以i-1為結(jié)尾的s，它的子序列中出現(xiàn)以j-1為結(jié)尾的t的個數(shù)為dp[i][j]-
狀態(tài)轉(zhuǎn)移方程：
-
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]
-
-
初始狀態(tài)：
-
dp[i][0] =1：當j=0時，相當于t是空字符串湃番，空字符在另一個字符串的子串中出現(xiàn)一次夭织，此時第一列都初始化為1。 - 其他情況：初始化的時候
dp[i][j] =0
-
復雜度：時間復雜度
O(mn)吠撮，m尊惰，n分別是s和t的長度。空間復雜度O(mn)弄屡，dp數(shù)組的空間
js：
//dp[i][j]表示以i-1為結(jié)尾的s子序列中出現(xiàn)以j-1為結(jié)尾的t的個數(shù)為dp[i][j]
const numDistinct = (s, t) => {
//初始化dp數(shù)組题禀，
let dp = Array.from(Array(s.length + 1), () => Array(t.length +1).fill(0));
//當j=0時，相當于t是空字符串膀捷，空字符在另一個字符串的子串中出現(xiàn)一次迈嘹，此時第一列都初始化為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()];
}
}
125. 驗證回文串 （easy）
思路：用正則去掉無關(guān)字符秀仲，然后對撞指針判斷左右兩邊是否是相同的字符
復雜度：時間復雜度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;
}
796. 旋轉(zhuǎn)字符串 (easy)
- 思路：字符串重復一次 判斷是否包含另一個字符串
- 復雜度：時間復雜度
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);
}
}
844. 比較含退格的字符串 (easy)
ds_184
方法1.截取字符串覆劈，循環(huán)字符串保礼，遇到#就截掉最后一個字符，循環(huán)完畢之后责语，最后比較兩個去除掉#退格之后的字符串是否相等氓英，時間復雜度O(m+n)，m鹦筹、n是兩個字符串的長度≈访玻空間復雜度O(1)
方法2.雙指針
- 思路：雙指針從右往左循環(huán)铐拐，每次循環(huán)兩個字符處理掉#，直到第一個字符是右邊退格全部處理掉之后的字符练对，然后看這兩個字符是否一致
- 復雜度：時間復雜度
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;
//雙指針從右往左循環(huán)
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--;//繼續(xù)循環(huán)
j--;
}
return true;//如果循環(huán)過程中沒返回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;
}
}
557. 反轉(zhuǎn)字符串中的單詞 III (easy)
方法1:借助api
// "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(' ');
};
方法2:雙指針
js：
// "Let's take LeetCode contest"
var reverseWords = function (s) {
let arr = s.split("");
let l = 0, r = l;
while (l < arr.length) {
//找到結(jié)尾的空格
while (arr[r] && arr[r] !== " ") {
r++;
}
//反轉(zhuǎn)單詞
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("");
};
