Longest Common Prefix
public class Solution {
/* int indexOf(int ch) 返回指定字符在此字符串中第一次出现处的索引。 int indexOf(int ch, int fromIndex) 从指定的索引开始搜索，返回在此字符串中第一次出现指定字符处的索引。 int indexOf(String str) 返回第一次出现的指定子字符串在此字符串中的索引。 int indexOf(String str, int fromIndex) 从指定的索引处开始，返回第一次出现的指定子字符串在此字符串中的索引。 *//* public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ""; String pre = strs[0]; int i = 1; while(i < strs.length){ while(strs[i].indexOf(pre) != 0){ pre = pre.substring(0, pre.length()-1); } i++; } return pre; } */ public String longestCommonPrefix(String[] strs) { if(strs.length == 0||strs == null) return ""; for(int i = 0; i<strs[0].length(); i++){ char x = strs[0].charAt(i); for(int j = 1; j<strs.length; j++){ if(strs[j].length() == i || strs[j].charAt(i) != x) //return strs[0].substring(0,i); strs[0] = strs[0].substring(0,i); // return strs[0]; } } return strs[0]; }}
Longest Common Substring (Java)
In computerscience, the longest common substring problem is to find the longest stringthat is a substring of two or more strings.
Java Solution
public static int getLongestCommonSubstring(String a, String b){
int m = a.length();
int n = b.length();
int max = 0;
int[][] dp = new int[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(a.charAt(i) == b.charAt(j)){
if(i==0 || j==0){
dp[i][j]=1;
}else{
dp[i][j] = dp[i-1][j-1]+1;
}
if(max < dp[i][j])
max = dp[i][j];
}
}
}
return max;
}
The longest common subsequence (LCS) problem is the problem offinding the longest subsequence common to all sequences in a set of sequences(often just two sequences).
Java Solution
public static int getLongestCommonSubsequence(String a, String b){ int m = a.length(); int n = b.length(); int[][] dp = new int[m+1][n+1]; for(int i=0; i<=m; i++){ for(int j=0; j<=n; j++){ if(i==0 || j==0){ dp[i][j]=0; }else if(a.charAt(i-1)==b.charAt(j-1)){ dp[i][j] = 1 + dp[i-1][j-1]; }else{ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }
publicintlengthOfLongestSubstring(String s){
if(s==null|| s.length()==0){
return0;
}
int start=0;
int max =0;
HashSet<Character> set =new HashSet<Character>();
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(!set.contains(c)){
set.add(c);
max =Math.max(max, i-start+1);
}else{
for(int j=start; j<i; j++){
set.remove(s.charAt(j));
if(s.charAt(j)==c){
start=j+1;
break;
}
}
set.add(c);
}
}
return max;
}
Leetcode – Longest Palindromic Substring (Java)
Finding thelongest palindromic substring is a classic problem of coding interview. Thispost summarizes 3 different solutions for this problem.
1. Dynamic Programming
Let s be theinput string, i and j are two indices of the string. Define a 2-dimension array"table" and let table[i][j] denote whether a substring from i to j ispalindrome.
Changingcondition:
table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)
=>
table[i][j] == 1
Time O(n^2)Space O(n^2)
public String longestPalindrome(String s) {
if(s==null || s.length()<=1)
return s;
int len = s.length();
int maxLen = 1;
boolean [][] dp = new boolean[len][len];
String longest = null;
for(int l=0; l<s.length(); l++){
for(int i=0; i<len-l; i++){
int j = i+l;
if(s.charAt(i)==s.charAt(j) && (j-i<=2||dp[i+1][j-1])){
dp[i][j]=true;
if(j-i+1>maxLen){
maxLen = j-i+1;
longest = s.substring(i, j+1);
}
}
}
}
return longest;
}
For example,if the input string is "dabcba", the final matrix would be thefollowing:
1 0 0 0 0 0
0 1 0 0 0 1
0 0 1 0 1 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
From thetable, we can clearly see that the longest string is in cell table[1][5].
2. A Simple Algorithm
Time O(n^2),Space O(1)
public String longestPalindrome(String s) {
if (s.isEmpty()) {
return null;
}
if (s.length() == 1) {
return s;
}
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
// get longest palindrome with center of i
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// get longest palindrome with center of i, i+1
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// Given a center, either one letter or two letter,
// Find longest palindrome
public String helper(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
return s.substring(begin + 1, end);
}
LeetCode – Shortest Palindrome (Java)
Given a string S, you are allowed toconvert it to a palindrome by adding characters in front of it. Find and returnthe shortest palindrome you can find by performing this transformation.
For example, given "aacecaaa",return "aaacecaaa"; given "abcd", return"dcbabcd".
Java Solution 1
public String shortestPalindrome(String s) {
int i=0;
int j=s.length()-1;
while(j>=0){
if(s.charAt(i)==s.charAt(j)){
i++;
}
j--;
}
if(i==s.length())
return s;
String suffix = s.substring(i);
String prefix = new StringBuilder(suffix).reverse().toString();
String mid = shortestPalindrome(s.substring(0, i));
return prefix+mid+suffix;
}
Java Solution 2
We can solvethis problem by using one of the methods which is used to solve the longest palindrome substring problem.
Specifically, we can start from thecenter and scan two sides. If read the left boundary, then the shortestpalindrome is identified.
public String shortestPalindrome(String s) {
if (s == null || s.length() <= 1)
return s;
String result = null;
int len = s.length();
int mid = len / 2;
for (int i = mid; i >= 1; i--) {
if (s.charAt(i) == s.charAt(i - 1)) {
if ((result = scanFromCenter(s, i - 1, i)) != null)
return result;
} else {
if ((result = scanFromCenter(s, i - 1, i - 1)) != null)
return result;
}
}
return result;
}
private String scanFromCenter(String s, int l, int r) {
int i = 1;
//scan from center to both sides
for (; l - i >= 0; i++) {
if (s.charAt(l - i) != s.charAt(r + i))
break;
}
//if not end at the beginning of s, return null
if (l - i >= 0)
return null;
StringBuilder sb = new StringBuilder(s.substring(r + i));
sb.reverse();
return sb.append(s).toString();
}
