1. Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
[Analysis]
一个DP问题。定义possible[i] 为S字符串上[0,i]的子串是否可以被segmented by dictionary.
那么
possible[i] = true if S[0,i]在dictionary里面
= true if possible[k] == true 并且 S[k+1,j]在dictionary里面， 0<k<i
= false if no such k exist.
[Code]
实现时前面加一个dummy节点，这样可以把三种情况统一到一个表达式里面。 时间复杂度O(n^2)
bool wordBreak(string s, unordered_set<string> &dict) {
string s2 = '#'+s;
int len = s2.size();
vector<bool> possible(len,0);
possible[0] = true;
for(int i=1;i<len;i++){
for(int k=0;k<i;k++){
possible[i] = possible[k] && dict.find(s2.substr(k+1,i-k))!=dict.end();
if(possible[i]) break;
}
}
return possible[len-1];
}
2. Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
定义函数
P[i,j] = 字符串区间[i,j]是否为palindrome.
首先找个例子，比如S="abccb",
S= a b c c b
Index = 0 1 2 3 4
P[0,0] =1 //each char is a palindrome
P[0,1] =S[0] == S[1] , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3], P[3,3]=1
......................
由此就可以推导出规律
P[i,j] = 1 if i ==j
= S[i] ==S[j] if j = i+1
= S[i] == S[j] && P[i+1][j-1] if j>i+1
实现如下：
public String longestPalindrome(String s) {
int len = s.length();
boolean [][] pal = new boolean[len][len];
for(int i=0;i<len;i++){
for(int j=0;j<len;j++)
pal[i][j] = false;
}
int start = 0;
int end = 0;
int mLen = 0;
for(int i=0;i<len;i++){
for(int j=0;j<i;j++){
pal[j][i] = (s.charAt(i)==s.charAt(j) && ((i-j<2) || pal[j+1][i-1]));
if(pal[j][i] && mLen<i-j+1){
mLen = i-j+1;
start = j;
end = i;
}
}
pal[i][i] = true;
}
return s.substring(start, end+1);
}
遍历整个字符串，以每个字符串为中心搜索回文并记录
c++
string longestPalindrome(string s) {
int startIndex = 0;
int len = 0;
int sI, eI;
for(int i=0; i< s.size()-1; i++){
if(s[i] == s[i+1]){
sI = i;
eI = i+1;
Search(s, sI, eI, len, startIndex);
}
sI = i;
eI = i;
Search(s, sI, eI, len, startIndex);
}
if(len ==0)
len = s.size();
return s.substr(startIndex,len);
}
void Search(string &s, int sI, int eI, int &len, int &startIndex){
int step = 1;
while((sI-step)>=0 && (eI+step)<s.size()){
if(s[sI-step] != s[eI+step])
{ break;}
step++;
}
int wid = eI-sI+2*step-1;
if(wid>len){
len = wid;
startIndex = sI-step +1;
}
}
3. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Analysis:
DP problem,
Transaction function: a[n][i] = a[n][i]+min(a[n-1][i], a[n-1][i-1]).
Note that in this problem, "adjacent" of a[i][j] means a[i-1][j] and a[i-1][j-1], if available(not out of bound), while a[i-1][j+1] is not "adjacent" element.
If we do this from up to down, it is complicated. While from down to up, we could use only one array to scan every row to get result
Java
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
if(n==0) return 0;
int m = triangle.get(n-1).size();
int [] result = new int[m];
for(int i=n-1;i>=0;i--){
for(int j=0;j<triangle.get(i).size();j++){
if(i==n-1){
result[j] = triangle.get(i).get(j);
continue;
}
result[j] = Math.min(result[j], result[j+1])+triangle.get(i).get(j);
}
}
return result[0];
}
c++
int minimumTotal(vector<vector<int> > &triangle) {
int row = triangle.size();
if(row == 0) return 0;
vector<int> minV(triangle[row-1].size());
for(int i = row-1; i>=0;i--){
int col = triangle[i].size();
for(int j=0; j<col;j++){
if(i==row-1){
minV[j] = triangle[i][j];
continue;
}
minV[j] = min(minV[j],minV[j+1])+triangle[i][j];
}
}
return minV[0];
}
4.
未完待续