目录
-
Reverse
-
SubString
-
Convert
-
Palindrome
-
Parentheses
-
Remove
基本String知识
- char[] --> string:
new String(c) - string --> char[]:
s.toCharArray() - int --> string:
Integer.toString(i) -
str.split(" ")str.trim() - StringBuilder x = new StringBuilder();
x.append(st + " ");x.toString()x.reverse()
#344 Reverse String
- Sol 遍历
public String reverseString(char[] c) {
for(int i = 0, j = c.length-1; i<=j;i++, j--){
char tmp = c[i];
c[i] = c[j];
c[j] = tmp;
}
return new String(c);
}
#541 Reverse String II
Easy
-
Sol
每隔k个字符就翻转k个字符，框架
ublic String reverseStr(String s, int k) {
cha[] c = s.toCharArray();
for(int i = 0; i < c.length; i += 2*k){
if(i+k >= length){
reverse(c, i, c.length-1);
}else{
reverse(c, i, i+k-1);
}
}
return new String(c);
}
翻转
public void reverse(char[] s, int start, int end){
while(start < end){
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
#557 Reverse Words in a String III
Easy
- Sol
public String reverseWords(String s) {
String[] word = s.split(" ");
StringBuilder res = new StringBuilder();
for(String si : word){
res.append(reverse(si) + " ");
}
return res.toString().trim();
}
public String reverse(String s){
char[] c = s.toCharArray();
for(int i = 0, j = c.length-1; i < j; i++, j--){
char tmp = c[i];
c[i] = c[j];
c[j] = tmp;
}
return new String(c);
}
#345 Reverse Vowels of a String
- Sol two pointer
public String reverseVowels(String s) {
char[] c = s.toCharArray();
for(int i = 0, j = c.length-1; i < j;){
boolean i_b = (c[j] == 'a' || c[j] == 'e' || c[j] == 'i' || c[j] == 'o' || c[j] == 'u' || c[j] == 'A' || c[j] == 'E' || c[j] == 'I' || c[j] == 'O' || c[j] == 'U');
boolean i_a = c[i] == 'a' || c[i] == 'e' || c[i] == 'i' || c[i] == 'o' || c[i] == 'u' || c[i] == 'A' || c[i] == 'E' || c[i] == 'I' || c[i] == 'O' || c[i] == 'U';
if(i_a && i_b){
char tmp = c[i];
c[i] = c[j];
c[j] = tmp;
i++;
j--;
}
if(!i_a){
i++;
}
if(!i_b){
j--;
}
}
return new String(c);
}
【SubString】
#1016 Binary String With Substrings Representing 1 To N
int to binary string / substring check
-
Sol built in function
int数的二进制表示Integer.toBinaryString(i)
判断一个字符串中是否包含某一 子字符串str.indexOf("china")!=-1
public boolean queryString(String S, int N) {
for(int i = 1; i <= N; i++){
String tmp = Integer.toBinaryString(i);
if(S.indexOf(tmp)==-1){return false;}
}
return true;
}
#647 Palindromic Substrings
计算回文子字符串的个数
-
Sol 动态规划|对称性
【对称轴】回文串都有某个对称轴（奇数个字符的串对称轴为最中间的字符。偶数不同，偶数的对称轴可以看做两个）.
【回文串的规律】当在回文串两端各加入两个相同的字符的时候，形成的新字符仍旧是回文串。
int count = 0;
public int countSubstrings(String s) {
for(int i = 0; i < s.length(); i++){
help(s, i, i); //奇数
help(s, i, i+1); //偶数
}
return count;
}
public void help(String s, int start, int end){
while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
count++;
start--;
end++;
}
}
#5 Longest Palindromic Substring
- Sol 类似647
class Solution {
int max_length = 0;
String res = "";
public String longestPalindrome(String s) {
for(int i = 0; i < s.length(); i++){
help(s, i, i);
help(s, i, i+1);
}
return res;
}
public void help(String s, int start, int end){
while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
int length = end - start + 1;
if(length > max_length){
max_length = length;
if(end+1 < s.length()) res = s.substring(start, end+1);
else res = s.substring(start);
}
start--;
end++;
}
}
}
#3 Longest Substring Without Repeating Characters
-
Sol HashMap
<字符，最后出现的位置>
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> m = new HashMap<>();
int length = s.length();
int i = 0, j = 0, res = 0;
while(i < length && j < length){
if(m.containsKey(s.charAt(j))){
i = Math.max(i, m.get(s.charAt(j))+1);
}
res = Math.max(res, j - i+1);
m.put(s.charAt(j), j);
j++;
}
return res;
}
#115 Distinct Subsequences
-
Sol DP
dp[i][j]表示s[0...j]包含的subsequence个数（==T[0...i]）
Base：dp[0][j] = 1, dp[i][0] = 0
Others：
if(s[j] == T[i]) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else dp[i][j] = dp[i][j-1];
public int numDistinct(String s, String t) {
int[][] dp = new int[t.length()+1][s.length()+1];
for(int i = 0; i <= t.length(); i++){
dp[i][0] = 0;
}
for(int j = 0; j <= s.length(); j++){
dp[0][j] = 1;
}
for(int i = 1; i <= t.length(); i++){
for(int j = 1; j <= s.length(); j++){
if(s.charAt(j-1) == t.charAt(i-1)){
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[t.length()][s.length()];
}
#459 Repeated Substring Pattern
- Sol One line
class Solution {
public boolean repeatedSubstringPattern(String s) {
return (s+s).substring(1, 2 * s.length() - 1).contains(s);
}
}
【Convert】
#13 Roman to Integer
- Sol map暂存
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> roman = new HashMap<>();
roman.put('I', 1);
roman.put('V', 5);
roman.put('X', 10);
roman.put('L', 50);
roman.put('C', 100);
roman.put('D', 500);
roman.put('M', 1000);
if(s.length() == 0) return 0;
int res = roman.get(s.charAt(0));
for(int i = 1; i < s.length(); i++){
if(roman.get(s.charAt(i)) > roman.get(s.charAt(i-1))){
res = res - 2 * roman.get(s.charAt(i-1)) + roman.get(s.charAt(i));
}else{
res += roman.get(s.charAt(i));
}
}
return res;
}
}
#12 Integer to Roman
- Sol 分情况考虑
public String intToRoman(int num) {
String res = "";
if(num >= 1000){
int a = num/1000;
while(a!=0){
res = res + "M";
num = num - 1000;
a--;
}
}
if(num >= 900){
res += "CM";
num = num - 900;
}
if(num >= 500){
res += "D";
num = num - 500;
}
if(num >= 400){
res += "CD";
num = num - 400;
}
while(num >= 100){
res += "C";
num = num-100;
}
if(num >= 90){
res += "XC";
num = num - 90;
}
if(num >= 50){
res += "L";
num = num - 50;
}
if(num >= 40){
res += "XL";
num = num -40;
}
while(num >= 10){
res += "X";
num = num-10;
}
if(num >=9){
res += "IX";
num = num - 9;
}
if(num >= 5){
res += "V";
num = num-5;
}
if(num == 4){
res += "IV";
num = num-4;
}
while(num > 0){
res += "I";
num--;
}
return res;
}
#273 Integer to English Words
- Sol
private final String[] belowTen = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
private final String[] belowTwenty = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] belowHundred = new String[] {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
return helper(num);
}
private String helper(int num) {
String result = new String();
if (num < 10) result = belowTen[num];
else if (num < 20) result = belowTwenty[num -10];
else if (num < 100) result = belowHundred[num/10] + " " + helper(num % 10);
else if (num < 1000) result = helper(num/100) + " Hundred " + helper(num % 100);
else if (num < 1000000) result = helper(num/1000) + " Thousand " + helper(num % 1000);
else if (num < 1000000000) result = helper(num/1000000) + " Million " + helper(num % 1000000);
else result = helper(num/1000000000) + " Billion " + helper(num % 1000000000);
return result.trim();
}
[Palindrome]
#125 Valid Palindrome
-
Sol
str = str.replaceAll("[a-zA-Z^0-9]", "");提取字符串中的字母数字
public boolean isPalindrome(String s) {
String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
String rev = new StringBuffer(actual).reverse().toString();
return actual.equals(rev);
}
#680 Valid Palindrome II
-
Sol Greedy
收尾依次判断，只允许有一个不同。检测（i++，j）||（i，j--）
public boolean validPalindrome(String s) {
char[] ch = s.toCharArray();
int n = s.length();
for(int i = 0, j = n-1; i < j; i++, j--){
if(ch[i] != ch[j]){
if(i + 1 == j) return true;
return help(s.substring(i, j)) || help(s.substring(i+1, j+1));
}
}
return true;
}
public boolean help(String s){
for(int i = 0, j = s.length()-1; i < j; i++, j--){
if(s.charAt(i) != s.charAt(j)) return false;
}
return true;
}
#131 Palindrome Partitioning
-
Sol DP + DFS
dp[i][j]表示s[i..j]是否是palindrome
boolean[][] dp;
List<List<String>> res;
public List<List<String>> partition(String s) {
int l = s.length();
res = new ArrayList<>();
dp = new boolean[l][l];
dpCreate(s);
dfs(0, s, new ArrayList<>());
return res;
}
public void dfs(int index, String s, List<String> cur){
if(index >= s.length()) {
res.add(new ArrayList<>(cur));
return;
}
for(int i = index; i < s.length(); i++){
if(dp[index][i]){
cur.add(s.substring(index, i+1));
dfs(i+1, s, cur);
cur.remove(cur.size()-1);
}
}
}
public void dpCreate(String s){
int l = s.length();
for(int i = 0; i < l; i++){
for(int j = 0; j < l; j++){
dp[i][j] = isParlindrome(s, i, j);
}
}
}
public boolean isParlindrome(String s, int i, int j){
for(;i<j;i++,j--){
if(s.charAt(i) != s.charAt(j)) return false;
}
return true;
}
#132 Palindrome Partitioning II
-
Sol dp
dp[i][j] 表示s[i...j]是都是palindrome
num[i]最小分割数s[0...i]
class Solution {
public int minCut(String s) {
int l = s.length();
char[] c = s.toCharArray();
boolean[][] dp = new boolean[l][l];
int[] num = new int[l];
for(int j = 0; j < l; j++){
int min = Integer.MAX_VALUE;
for(int i = 0; i <= j; i++){
if(c[i] == c[j] && (i+1>=j || dp[i+1][j-1])){
dp[i][j] = true;
min = (i == 0 ? 0 : Math.min(min, num[i-1] + 1));
}
}
num[j] = min;
}
return num[l-1];
}
}
#214 Shortest Palindrome
-
Sol1 Two pointer + Recursion
i从左至右遍历，j右至左遍历
Time O(n^2)：worst case，每次递归，string分为两部分T(n)=T(n−2)+O(n)=
O(n)+O(n−2)+O(n−4)+...+O(1) = O(n^2)
Space O(n)存reverse string
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
int i = 0;
for(int j = n-1; j >= 0; j--){
if(s.charAt(i) == s.charAt(j)) i++;
}
if(i == n) return s;
String reverse = rev(s.substring(i));
return reverse + shortestPalindrome(s.substring(0, i)) + s.substring(i);
}
public String rev(String s){
char[] cc = s.toCharArray();
int n = s.length();
for(int i = 0, j = n-1; i < j; i++, j--){
char c = cc[i];
cc[i] = cc[j];
cc[j] = c;
}
return new String(cc);
}
}
-
Sol2 KMP
Knuth-Morris-Pratt字符串查找算法，reverse(s) + '#' + s组成新string，找出新字符串前缀后缀相等的最大长度
class Solution {
public String shortestPalindrome(String s) {
String reverse = rev(s);
String s_new = s + "#" + reverse;
int len = s_new.length();
int[] table = new int[len];
for(int i = 1; i < len; i++) {
int t = table[i-1];
while(t > 0 && s_new.charAt(i) != s_new.charAt(t))
t = table[t-1];
if(s_new.charAt(i) == s_new.charAt(t))
++t;
table[i] = t;
}
return reverse.substring(0, s.length()-table[len-1]) + s;
}
public String rev(String s){
char[] cc = s.toCharArray();
int n = s.length();
for(int i = 0, j = n-1; i < j; i++, j--){
char c = cc[i];
cc[i] = cc[j];
cc[j] = c;
}
return new String(cc);
}
}
[Parentheses]
#20 Valid Parentheses
- Sol Stack
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
Map<Character, Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
for(int i = 0; i < s.length(); i++){
// char c = s.charAt(i);
if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
st.push(s.charAt(i));
}else{
if(st.isEmpty()) return false;
char c = st.pop();
if(c != map.get(s.charAt(i))) return false;
}
}
return st.isEmpty();
}
#22 Generate Parentheses
- Sol (left) + right
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if(n==0){
res.add("");
return res;
}
for(int i = 0; i < n; i++){
for(String left: generateParenthesis(i)){
for(String right: generateParenthesis(n-i-1)){
res.add("("+left+")" + right);
}
}
}
return res;
}
#32 Longest Valid Parentheses
-
Sol
分别从左从右遍历string，计算left与right的值，一旦相等，更新max。
public int longestValidParentheses(String s) {
int left = 0, right = 0;
int max = 0;
// int start = 0;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '('){
left++;
}
if(c == ')') right++;
if(left == right) max = Math.max(max, 2 * right);
else if(right > left){
right = 0;
left = 0;
}
}
right = 0;
left = 0;
for(int i = s.length()-1; i >= 0 ; i--){
char c = s.charAt(i);
if(c == '('){
left++;
}
if(c == ')') right++;
if(left == right) max = Math.max(max, 2 * right);
else if(left > right){
right = 0;
left = 0;
}
}
return max;
}
Time complexity : O(n). Two traversals of the string.
Space complexity : O(1). Only two extra variables leftleft and rightright are needed.
#241 Different Ways to Add Parentheses
-
Sol DP
map<String, list<Integer>>
Map<String, List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
if(map.containsKey(input)) return map.get(input);
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < input.length(); i++){
if(!Character.isDigit(input.charAt(i))){
for(int a: diffWaysToCompute(input.substring(0,i))){
for(int b: diffWaysToCompute(input.substring(i+1))){
ans.add(input.charAt(i) == '+'?a+b:input.charAt(i) == '-'?a-b:a*b);
}
}
}
}
if(ans.isEmpty()) ans.add(Integer.parseInt(input));
map.put(input, ans);
return ans;
}
#301 Remove Invalid Parentheses
- Sol DFS
public List<String> removeInvalidParentheses(String s) {
List<String> res = new ArrayList<>();
List<String> candidate = new ArrayList();
Set<String> set = new HashSet<>();
candidate.add(s);
while(!candidate.isEmpty()){
for(String p: candidate){
if(isValid(p)) res.add(p);
}
if(!res.isEmpty()) return res;
List<String> next = new ArrayList();
for(String p: candidate){
for(int i = 0; i < p.length(); i++){
if(p.charAt(i)!='(' && p.charAt(i)!=')') continue;
String ne = p.substring(0,i)+p.substring(i+1);
if(!set.contains(ne)){
next.add(ne);
set.add(ne);
}
}
}
candidate = next;
}
return res;
}
public boolean isValid(String s){
char[] c = s.toCharArray();
int count = 0;
for(int i = 0; i < c.length; i++){
if(c[i]=='(') count++;
if(c[i] == ')') count--;
if(count < 0) return false;
}
return count==0;
}
[Remove]
#316 Remove Duplicate Letters
-
Sol StringBuilder
Space O(n)
Time O(n)
class Solution {
public String removeDuplicateLetters(String s) {
StringBuilder sb = new StringBuilder();
int[] count = new int[26];
boolean[] visited = new boolean[26];
for(char c: s.toCharArray()){
count[c-'a']++;
}
for(char c: s.toCharArray()){
count[c-'a']--;
if(!visited[c-'a']){
while(sb.length()>0 && c < sb.charAt(sb.length()-1) && count[sb.charAt(sb.length() - 1) - 'a'] > 0){
visited[sb.charAt(sb.length() - 1) - 'a'] = false;
sb.setLength(sb.length() - 1);
}
sb.append(c);
visited[c-'a'] = true;
}
}
return sb.toString();
}
}
