分治方法
- 將問題劃分成互不相交的子問題
- 遞歸地求解子問題
- 將子問題的解組合起來
動態(tài)規(guī)劃(兩個要素：最優(yōu)子結(jié)構(gòu)木西、子問題重疊)
- 應(yīng)用于子問題重疊的情況为黎，對于每個子問題求解一次年栓，并將結(jié)果放在表格中
- 通常用于求解最優(yōu)化問題或和問題
- 找出子問題铆惑，定義最優(yōu)子結(jié)構(gòu)=> 給出最優(yōu)子結(jié)構(gòu)的遞推公式 => 計算最優(yōu)解（通常Bottom-top）
70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
斐波那契數(shù)列利职。子問題F(n)為到第n階階梯的不同走法。最優(yōu)子結(jié)構(gòu)：F(n) = F(n - 1) + F(n - 2)糟红。
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int left = 1, right = 2, next = 0;
for (int i = 3; i <= n; ++i) {
next = left + right;
left = right;
right = next;
}
return next;
}
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
最優(yōu)化問題艾帐，通常使用DP可以解決。
1.子問題maxSubArray(int A[], i)代表[0, i]的最大子序列
2.最優(yōu)子結(jié)構(gòu)maxSubArray(int[], i) = (maxSubArray(int[], i - 1) > 0 ? maxSubArray(int[], i - 1) : 0) + A[i]
3.求解盆偿，使用Bottom-top自底向上柒爸，計算從i=0到n-1的情況
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN, curSum = INT_MIN;
for (auto n:nums) {
if (curSum > 0) curSum += n;
else curSum = n;
maxSum = max(maxSum, curSum);
}
return maxSum;
}
152. Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
求數(shù)組中連續(xù)乘積的最大值。雙向乘法事扭，從前向后以及從后向前捎稚。子問題：curMax = max(leftProduct, rightProduct)
int maxProduct(vector<int>& nums) {
if (nums.empty()) return 0;
int leftProduct = 1, rightProduct = 1, curMax = INT_MIN;
for (auto i = 0; i < nums.size(); ++i) {
leftProduct *= nums[i];
rightProduct *= nums[nums.size() - 1 - i];
curMax = max(curMax, max(leftProduct, rightProduct));
if (!leftProduct) leftProduct = 1;
if (!rightProduct) rightProduct = 1;
}
return curMax;
}
62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
m行n列，從[0, 0]到[m-1, n-1]一共有多少種走法求橄。子問題path[i][j]為到達[i,j]位置的路徑數(shù)今野，最優(yōu)子結(jié)構(gòu)為：path[i][j] = path[i-1][j] + path[i][j-1]
int uniquePaths(int m, int n) {
if (m > n) swap(m, n);
vector<int> path(m, 1);
for (int i = 1; i < n; ++i)
for (int j = 1; j < m; ++j)
path[j] += path[j-1];
return path.back();
}
63. Unique Paths II
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
m行n列，從[0, 0]到[m-1, n-1]一共有多少種走法罐农。其中存在障礙腥泥。子問題path[i][j]為到達[i,j]位置的路徑數(shù)，最優(yōu)子結(jié)構(gòu)為：dp[i][j] =0啃匿，當(dāng)obstacleGrid[i][j] == 1時; dp[i][j] = dp[i-1][j] + dp[i][j-1]，當(dāng)當(dāng)obstacleGrid[i][j] == 0時。 使用了m+1*n+1的結(jié)果矩陣來保存結(jié)果溯乒，將obstacleGrid[0][0]為0和為1的情況做了統(tǒng)一處理夹厌。
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[0][1] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (grid[i-1][j-1] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
return dp[m][n];
}
64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
從[0, 0]到[n-1, n-1]的最短路徑。
- 子問題：到達[i,j]只有從上往下或從左往右兩條路
- 最優(yōu)子結(jié)構(gòu)：dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1]
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));
dp[0][1] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1];
}
}
return dp[m][n];
}
120. Triangle
iven 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).
到達某個點可用之前鄰居的鄰居裆悄，子問題有重疊矛纹。找和最小的路徑，是最優(yōu)化問題光稼。子問題：sum[i][j]為從底向上或南，到達第i行第j列的最小路徑和。最優(yōu)子結(jié)構(gòu)為：sum[i][j] = min(sum[i+1][j], sum[i+1][j+1]) + triangle[i][j]
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
if (!m) return 0;
vector<int> sum(triangle.back());
for (int i = m - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
sum[j] = min(sum[j], sum[j+1]) + triangle[i][j];
}
}
return sum[0];
}
96. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
求1..n直接整數(shù)構(gòu)成的不同二叉搜索樹的個數(shù)艾君。
- 子問題：G(n) = F(1, n) + F(2, n) + ... + F(n, n)且F(j, i) = G(j - 1)*G(i - j)
- 最優(yōu)子結(jié)構(gòu)：res[i] = res[1-1]res[i-1] + res[2-1]res[i-2] + ... + res[j-1]res[i-j] + ...+ res[i-1]res[i-i]
其中res(n)代表1..n構(gòu)成不同樹的個數(shù)采够；F(i, n)代表根節(jié)點為i時，1..n構(gòu)成不同二叉搜索樹的個數(shù)
int numTrees(int n) {
vector<int> res(n+1, 0);
res[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
res[i] += res[j-1]*res[i-j];
}
}
return res[n];
}
85. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
解析: 找出中為1的長方形的最大元素個數(shù)
思路：對于這種無從下手的矩陣問題肯定是一行行進行遍歷冰垄，而且有很大可能是動態(tài)規(guī)劃問題蹬癌。
1. height[j]為某列高度，left[j]為滿足該列高度的最左位置虹茶，right[j]為滿足該高度的最右位置+1
2. curLeft為從左往右第一個為1的位置逝薪，curRight為從右往左第一個為1的下一個位置。
3. left[j]=max(left[j], curLeft); right[j] = min(right[j], curRight);
4. res = max(res, (right[j] - left[j])*height[j]);
class Solution {public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int cur_left=0, cur_right=n;
for(int j=0; j<n; j++) { // compute height (can do this from either side)
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// compute right (from right to left)
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n; cur_right=j;}
}
// compute the area of rectangle (can do this from either side)
for(int j=0; j<n; j++)
maxA = max(maxA,(right[j]-left[j])*height[j]);
}
return maxA;
}
121. Best Time to Buy and Sell Stock
求最大收益蝴罪，只允許交易一次（此處用到了遍歷的順序董济，賣出必然在買入之后，所以直接求最大和最小值只差是不可以的）要门。
- 子問題： maxPro[i] = max(maxPro[i-1], cur - minProce)
- 最優(yōu)子結(jié)構(gòu)：maxPro = max(maxPro, prices[i] - minPrice)
時間復(fù)雜度：O(n)
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX, maxPro = 0;
for (int i = 0; i < prices.size(); ++i) {
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}
123. Best Time to Buy and Sell Stock III
思路：動態(tài)規(guī)劃虏肾。這個很難想，很想121中第一種方法暂衡，主要區(qū)別是本次可以多于2次交易询微，第2次不能和第一次重復(fù)，所以要用lowBuyPrice1 = min(lowBuyPrice1, p - maxProfit1)狂巢，將第一次交易獲得利潤保存在第二次購買的價格中撑毛。又變成了單次交易最大獲利。 子狀態(tài)為：每次第一次獲利找出最大的2次獲利和唧领，最終會找到最大獲利藻雌。
- 子問題：maxPro = max(sell1-buy1 + sell2-buy2)
- 最優(yōu)子結(jié)構(gòu)： maxPro = max(maxPro, sell2 - (buy2 - maxPro1))
int maxProfit(vector<int>& prices) {
int maxProfit1 = 0, maxProfit2 = 0;
int lowBuyPrice1 = INT_MAX, lowBuyPrice2 = INT_MAX;
for (auto p:prices) {
lowBuyPrice1 = min(lowBuyPrice1, p);
maxProfit1 = max(maxProfit1, p - lowBuyPrice1);
lowBuyPrice2 = min(lowBuyPrice2, p - maxProfit1);
maxProfit2 = max(maxProfit2, p - lowBuyPrice2);
}
return maxProfit2;
}
188. Best Time to Buy and Sell Stock IV
思路：動態(tài)規(guī)劃。思路和最多買賣2次的很像斩个，區(qū)別在k>n/2時需要特殊處理胯杭，不然會溢出，k>n/2時就能取交易的最大數(shù)目受啥，因為不需要買賣之間可以一段做个。
時間復(fù)雜度：O(kn) 空間復(fù)雜度O(k)
int maxProfit(int k, vector<int>& prices) {
int maxProfit = 0;
if (k < 1) return 0;
if(prices.size()<2)
return 0;
if(k>prices.size()/2){
for(int i=1; i<prices.size(); i++)
maxProfit += max(prices[i]-prices[i-1], 0);
return maxProfit;
}
vector<int> lowBuyPrice(k,INT_MAX), maxPro(k, 0);
for (auto p:prices) {
for (int i = 0; i < k; ++i) {
lowBuyPrice[i] = min(lowBuyPrice[i], i == 0 ?p:p - maxPro[i-1]);
maxPro[i] = max(maxPro[i], p - lowBuyPrice[i]);
}
}
return maxPro.back();
}
95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
96題升級版鸽心，求[1,n]構(gòu)成的全部平衡二叉樹。
- 子問題：G(n) = F(1, n) + F(2, n) + ... + F(n, n)且F(j, i) = G(j - 1)*G(i - j)
- 最優(yōu)子結(jié)構(gòu)：res[i] = res[1-1]res[i-1] + res[2-1]res[i-2] + ... + res[j-1]res[i-j] + ...+ res[i-1]res[i-i]
此處使用小技巧居暖，使用offset拷貝res[i-j]為j的右子樹
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
if (!n) return vector<TreeNode*>();
vector<vector<TreeNode*>> res(n+1, vector<TreeNode*>());
res[0].push_back(NULL);
for (int i = 1; i <=n; ++i) {
for (int j = 1; j <= i; ++j) {
for (auto l:res[j-1]) {
for (auto r:res[i-j]) {
TreeNode* node = new TreeNode(j);
node->left = l;
node->right = clone(r, j);
res[i].push_back(node);
}
}
}
}
return res[n];
}
TreeNode* clone(TreeNode* root, int offset){
if(root == nullptr)
return nullptr;
TreeNode* newroot = new TreeNode(root->val + offset);
newroot->left = clone(root->left, offset);
newroot->right = clone(root->right, offset);
return newroot;
}
};
也可以使用分治的方法求解顽频，子問題會重復(fù)求解。然而這倆個解的實際運行實際都是19ms太闺，原因是動態(tài)規(guī)劃的部分由于數(shù)組中保存的是指針糯景，所以即使保存了子問題的解，仍然需要使用clone函數(shù)將子問題的解重新分配空間省骂。
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
if (!n) return vector<TreeNode*>();
return helper(1, n);
}
vector<TreeNode *> helper(int s, int e){
vector<TreeNode*> res;
if (s > e) {
res.push_back(NULL);
return res;
}
for (int i = s; i <= e; ++i) {
auto left = helper(s, i-1);
auto right = helper(i+1, e);
for (auto l:left) {
for (auto r:right) {
TreeNode *node = new TreeNode(i);
node->left = l;
node->right = r;
res.push_back(node);
}
}
}
return res;
}
};
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
求數(shù)字字符串解碼的個數(shù)蟀淮。
- 子問題：依次遍歷字符串，主要分為2種情況钞澳，當(dāng)前字符不為0怠惶；當(dāng)前和前一個字符構(gòu)成的數(shù)字在1-26之間。
- 最優(yōu)子結(jié)構(gòu)：count[i] = count[i-1]isNotZero(s,i) + count[i-2]isLastTwoLess26(s, i)略贮。
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int first = 1, second = 1;
for (auto i = 1; i < s.size(); ++i) {
int tmp = 0;
if (s[i] > '0' && s[i] <= '9')
tmp += second;
if ((s[i-1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i-1] == '2' && s[i] >= '0' && s[i] <= '6'))
tmp += first;
first = second;
second = tmp;
}
return second;
}
89. Gray Code
生成格雷碼甚疟，對于輸入n，輸出2^n個int逃延。
最優(yōu)子結(jié)構(gòu)： G(n) = B(n) XOR B(n)/2
vector<int> grayCode(int n) {
vector<int> res;
for (int i = 0; i < 1<<n; ++i) {
res.push_back(i^(i>>1));
}
return res;
}
詳解览妖。
97. Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
第三個字符串是否是前兩個字符串交叉拼接起來的。使用矩陣記錄table[i][j]記錄是否s3[i+j-1]是可以使用s1[0..i-1]揽祥、s2[0..j-1]拼接起來讽膏。注意啞變量的使用。
子問題：第三個字符串可以分割為前兩個字符串的依次遍歷拄丰。
最優(yōu)子結(jié)構(gòu)：table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1]) || (table[i][j-1] && s2[j-1] == s3[i+j-1])
bool isInterleave(string s1, string s2, string s3) {
if (s3.size() != s1.size() + s2.size()) return false;
vector<vector<bool>> table(s1.size() + 1, vector<bool>(false, s2.size() + 1));
for (auto i = 0; i <= s1.size(); ++i) {
for (auto j = 0; j <= s2.size(); ++j) {
if (i == 0 && j == 0)
table[i][j] = true;
else if (i == 0)
table[0][j] = (table[0][j-1] && s2[j-1] == s3[j-1]);
else if (j == 0)
table[i][0] = (table[i-1][0] && s1[i-1] == s3[i-1]);
else
table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1]) || (table[i][j-1] && s2[j-1] == s3[i+j-1]);
}
}
return table[s1.size()][s2.size()];
}
72. Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
求最短的編輯距離府树。詳解
1. dp[i][j]代表word1[0..i-1]和word2[0..j-1]的最小編輯距離，大小為(m+1)*(n+1)
2. 最優(yōu)子結(jié)構(gòu)的遞推公式
dp[i][0] = i;
dp[0][j] = j;
dp[i][j] = dp[i - 1][j - 1], if word1[i - 1] = word2[j - 1];
dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1), otherwise.
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; ++i) dp[i][0] = i;
for (int j = 1; j <= n; ++j) dp[0][j] = j;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
else {
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
}
}
}
return dp[m][n];
}
拓展：該題目和經(jīng)典的LCS（最長公共子串）很像料按，都是通過保存大小為(m+1)*(n+1)的dp二維數(shù)組進行運算奄侠。
dp[i,j] = 0 \\若i = 0 或 j = 0
dp[i,j] = dp[i-1, j-1] + 1 \\若word1[i] = word2[j]
dp[i,j] = max(dp[i][j-1], dp[i-1][j]) \\若word1[i] != word2[j]
int lcs(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; ++i) dp[i][0] = 0;
for (int j = 1; j <= n; ++j) dp[0][j] = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp[m][n];
}
139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
求字符串是否可以使用詞典中詞分割。1. 子問題：dp[i]代表s[0..i-1]是否能分割 2. 最優(yōu)子結(jié)構(gòu)遞推公式： 對應(yīng)j[0, i]载矿，若存在dp[j] && 字典中存在s[j..i-1]垄潮， dp[i]為true。
bool wordBreak(string s, vector<string>& wordDict) {
// dp[i]代表s[0..i-1]是否可分割
unordered_set<string> dict;
for (auto word:wordDict) dict.insert(word);
auto m = s.size();
vector<bool> dp(m+1,false);
dp[0] = true;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
dp[i] = true;
break;
}
}
}
return dp[m];
}
140. Word Break II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
如果采用139題中使用的方法闷盔，記錄每個循環(huán)可用的會導(dǎo)致內(nèi)存不足的問題弯洗。使用下面的方式可用解決該問題，本質(zhì)上是BFS和DFS的區(qū)別逢勾。
- 子問題：wordBreak(s)為s對應(yīng)的可以分割的情況牡整。wordBreak(s) = wordBreak(left) + wordBreak(right)
- 最優(yōu)子結(jié)構(gòu)遞推公式： wordBreak(s) = wordBreak(left) + wordBreak(right)
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
if (m.count(s)) return m[s];
vector<string> res;
if (find(wordDict.begin(), wordDict.end(), s) != wordDict.end())
res.push_back(s);
for (auto i = 1; i < s.size(); ++i) {
string left = s.substr(0, i);
if (find(wordDict.begin(), wordDict.end(), left) != wordDict.end()) {
string right = s.substr(i);
vector<string> rest = wordBreak(right, wordDict);
for (auto &word:rest) {
word = left + " " + word;
}
res.insert(res.end(), rest.begin(), rest.end());
}
}
m[s] = res;
return res;
}
private:
unordered_map<string, vector<string>> m;
};
87. Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
字符串某個點為軸交互字符串兩邊，遞歸的進行上述操作可以得到的字符串為Scramble字符串溺拱。
- 子問題：isScramble(s1, s2) = pivot(1) || pivot(2) || ... || pivot(i) || ... || pivot(n-1)
- 最優(yōu)子結(jié)構(gòu)：pivot(i) = isScramble(s1[0..i-1], s2[i..n-1]) && isScramble(s1[i..n-1], s2[i..n-1]) || isScramble(s1[0..i-1], s2[n-i..n-1]) && isScramble(s1[i..n-1], s2[0..n-1-i])逃贝。即是兩個字符串左右對應(yīng)或交叉對應(yīng)谣辞。
bool isScramble(string s1, string s2) {
if (s1 == s2) return true;
string s1_tmp = s1;
string s2_tmp = s2;
std::sort(s1_tmp.begin(), s1_tmp.end());
std::sort(s2_tmp.begin(), s2_tmp.end());
if (s1_tmp != s2_tmp) return false;
for (int i = 1; i < s1.size(); ++i) {
if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) return true;
if (isScramble(s1.substr(0, i), s2.substr(s1.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s1.size() - i))) return true;
}
return false;
}
115. Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
刪除某些字符構(gòu)成不同的為目標(biāo)子串的個數(shù)。
- 子問題：table[i][j]中保存S[0..j-1]包含T[0..i-1]個不同的子串沐扳。
- 最優(yōu)子結(jié)構(gòu)：如果S[j] == T[i]潦闲，則table[i][j] = table[i-1][j-1] + table[i][j-1]。（之前有的+各短一個字母的S和T）迫皱。
int numDistinct(string s, string t) {
vector<vector<int>> table(t.size()+1, vector<int>(s.size()+1, 0));
for (auto j = 0; j < s.size(); ++j) table[0][j] = 1;
for (int i = 1; i <= t.size(); ++i) {
for (int j = 1; j <= s.size(); ++j) {
if (s[j-1] == t[i-1])
table[i][j] = table[i][j-1] + table[i-1][j-1];
else
table[i][j] = table[i][j-1];
}
}
return table[t.size()][s.size()];
}
132. Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
求將字符串分割成回文子串的最小割。dp[i]代表s[0:i)的最小回文割樹辖众。
- i為中點卓起，j為一半的長度。
- 最優(yōu)子結(jié)構(gòu)：如果s[i:j)構(gòu)成回文凹炸，則dp[j] = min(dp[j], dp[i] + 1)
int minCut(string s) {
auto m = s.size();
vector<int> dp(m+1, 0);
for (auto i = 0; i <= m; ++i) {
dp[i] = i - 1;
}
for (auto i = 0; i < m; ++i) {
for (auto j = 0; i-j >= 0 && i+j < m && s[i-j] == s[i+j]; ++j)
dp[i+j+1] = min(dp[i+j+1], dp[i-j] + 1);
for (auto j = 1; i-j+1 >=0 && i+j < m && s[i-j+1] == s[i+j]; ++j)
dp[i+j+1] = min(dp[i+j+1], dp[i-j+1] + 1);
}
return dp[m];
}
