Posts Tagged ‘string’
- In: classic | summery
- Leave a Comment
比如abcdefg, defmnabs，最长公共subtring是def。
又是二维DP求String的最优解。居然还是算法课作业做过，真是一点印象也木有了。
- d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
- d[i][j] =
- A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
- A[i] != B[j] : d[i][j] = 0//断开了，无公共后缀了
总结一下二维DP解String题的做法：
- 一个String, d[i][j]表示A[i…j]的某个最优解
- 两个String, d[i][j]表示A[0…i], B[0…j]的某个比较方式的最优解
- In: leetcode
- 3 Comments
这是好难好难的二维DP题。尽管知道两个String比较很可能是二维DP，但是状态方程真是不好定义；定义了关系也特别不直观。
A: RABBBIT; B: RABBIT
- d[i][j]: A[0…i]里面出现了几次B[0…j]，比如RAB里出现了几次RA
- d[i][j] =
- if A[i] != B[j]，比如RABC和RAB，那么C(A[i]就得被删除，d[i][j]就是RAB在RAB包含的之前算过的情况d[i – 1][j]
- if A[i] == B[j]，比如RABB和RAB，那么
- 可以把RABB的第二个B删除得到RAB，所以d[i][j]最少也是d[i – 1][j]
- 可以用RABB的第二个B直接对应RAB的那个B消掉，所以相当于A=RAB和B=RA，d[i][j] += d[i – 1][j – 1]
- 初始值就是二维DP那么做就行了。
- 这个是真心难想通。还得多做多练习。
public int numDistinct(String S, String T) {
if (T.length() > S.length())
return 0;
char[] A = S.toCharArray();
char[] B = T.toCharArray();
int[][] d = new int [A.length][B.length];
d[0][0] = A[0] == B[0] ? 1 : 0;
int count = d[0][0];
for (int i = 1; i < A.length; i++) {
if (A[i] == B[0])
count++;
d[i][0] = count;
}
for (int j = 1; j < B.length; j++) {
d[0][j] = 0;
}
for (int i = 1; i < A.length; i++) {
for (int j = 1; j < B.length; j++) {
if (A[i] == B[j]) {
d[i][j] = d[i - 1][j] + d[i - 1][j - 1];
} else {
d[i][j] = d[i - 1][j];
}
}
}
return d[A.length - 1][B.length - 1];
}
这题正经做了一段时间；首先自己想的算法不好，不够数学；另外这个题的testcase很多情况，自己没想清楚，全是用oj来查出错误了。
数学的做法：每个zigzag（|/形状是n + n – 2的长度；除非n < 2, 则就是n本身的长度），这样可以直接在string上跳着取出应该append的index。这个有两种情况：
ABCDEFGHIJKL n = 4 ------------- A G B F H L C E I K D J
- 第一行和最后一行每个zigzag段只要append一个就行了
- 中间那些行每次要append两个字母；
两个变量，想了半天。分别是“在当前段里的offset”和”在哪个zigzag段里“，但是要保证以”在那个段里“外层循环。
注意：想不明白边界条件的时候，不妨直接用if（边界在string range里），这样就能把所有出界全接住了。
public String convert(String s, int nRows) {
if (s == null)
return null;
int len = nRows <= 1 ? nRows : (2 * nRows - 2);
StringBuilder sb = new StringBuilder();
for (int offset = 0; offset < nRows; offset++) {
for (int zigIndex = 0; zigIndex * len < s.length(); zigIndex++) {
int firstIndex = zigIndex * len + offset;
if (firstIndex >= 0 && firstIndex < s.length())
sb.append(s.charAt(firstIndex));
if (offset > 0 && offset < nRows - 1) {
int reverseIndex = (zigIndex + 1) * len - offset;
if (reverseIndex >= 0 && reverseIndex < s.length())
sb.append(s.charAt(reverseIndex));
}
}
}
return sb.toString();
}
- In: 面经
- Leave a Comment
Given a string, find longest substring which contains just two unique characters. 比如ABACDDCB, 返回CDDC。
自己做的O(n)的解法，不用额外空间，但是需要additional data structure。测了几个没问题。
思路：假设d[i – 1]是以arr[i – 1]为结尾的data，已经做好了。那d[i] =
- 如果arr[i]属于d[i – 1]的那个substring中的两个元素中的某一个，那么d[i]的长度直接是上一个加一。
- 不属于的话，要把arr[i]和上一个的“最后一段由一个字母组成的sequance“连起来。比如d[i – 1]的结果是BABB，然后arr[i]是C，就想把BB和C连起来生成新的substring BBC然后放在d[i]里。
- 这样的话，需要记录四个数据：length, index of last sequence ‘s beginning m, the char that is not the last (in above case, is A), and last letter (B)（这个不是必要的，可以用m来读，但是看着方便。
public class Data {
int len;
Character last;
Character notLast;
int m;// beginning index of last sequense
}
String findLongestSubString(String s) {
if (s.length() == 0)
return null;
Data prev = new Data(1, s.charAt(0), null, 0);
Data maxData = prev;
int maxEnd = 0;
for (int i = 1; i < s.length(); i++) {
Data curr = new Data();
Character charAtI = s.charAt(i);
if (charAtI.equals(prev.last) || prev.notLast == null || charAtI.equals(prev.notLast)) {
curr.len = prev.len + 1;
curr.notLast = charAtI.equals(prev.last) ? prev.notLast : prev.last;
curr.last = s.charAt(i);
curr.m = charAtI.equals(prev.last) ? curr.m : i;
} else {
curr.len = i - prev.m + 1;
curr.notLast = prev.last;
curr.last = s.charAt(i);
curr.m = i;
}
if (curr.len > maxData.len) {
maxData = curr;
maxEnd = i;
}
prev = curr;
}
String result = s.substring(maxEnd - maxData.len + 1, maxEnd + 1);
return result;
}
Tags: string
example: aabc matches c*a*b.
思路：
- 两个指针i, j，i指regular expression，j指真的string。
- 观察p[i+1]，
- 如果它不是*，说明没法skip p[i]，则p[i]和s[j]必须match（相等或者p[i]是’.’ which matches everything）。如果不满足，直接返回false，没法matche了。
- 如果它是*，说明当前位置可以是0个p[i], 1个p[i], 2个p[i]..
- 先试试“用0个p[i]“，即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了，直接返回true，不成功，接着做第二步。
- 从“用1个p[i]“开始while循环，若p[i]和s[j] match, recurse on (i + 2, j + 1)（把*用掉了所以i+2），如果返回true就直接成了，否则就while继续循环“用2个p[i]“，即recurse on (i + 2, j + 2), recurse on (i + 2, j + 3)…循环的终止条件是p[i]和s[j]不match了，直接返回false。
public boolean isMatch(String s, String p) {
return tryMatch(p, s, 0, 0);
}
private boolean tryMatch(String p, String s, int i, int j) {
if (i == p.length())
return j == s.length();
if (i == p.length() - 1 || p.charAt(i + 1) != '*') { //下一个字母不是*，当前字母必须match
if (matchChar(p, s, i, j))
return tryMatch(p, s, i + 1, j + 1);
else
return false;
} else { // p[i + 1] is *
boolean skip = tryMatch(p, s, i + 2, j); //把当前字母去掉能行，就直接返回
if (skip)
return true;
while (matchChar(p, s, i, j)) {//*当一个p[i]开始，当两个，当三个。。
if (tryMatch(p, s, i + 2, j + 1))
return true;
j++;
}
return false;
}
}
private boolean matchChar(String p, String s, int i, int j) {
if (i >= p.length() || j >= s.length())
return false;
return p.charAt(i) == s.charAt(j) || p.charAt(i) == '.';
}
这应该是DFS，和CC上那道题也很像，但是实在是做不出来。。而且用binary分解那种方法想出来了，但是时间复杂度也弄不明白。崩溃了。这样下去，周一的MS会挂把。。。
———————–两个月之后———————-
一次Bugfree。看来人真是会成长的。。和word break一样做，abaa先分成a, baa，然后再分成ab, aa，左边是palindrome才recurse on右边：
public ArrayList<ArrayList<String>> partition(String s) {
Map<String, ArrayList<ArrayList<String>>> cache = new HashMap<String, ArrayList<ArrayList<String>>>();
return partition(s, cache);
}
private ArrayList<ArrayList<String>> partition(String s, Map<String, ArrayList<ArrayList<String>>> cache) {
if (cache.containsKey(s))
return cache.get(s);
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
if (s.isEmpty()) {
result.add(new ArrayList<String>());
}
for (int i = 0; i < s.length(); i++) {
String left = s.substring(0, i + 1);
if (isPalindrom(left)) {
String right = s.substring(i + 1);// right maybe empty
ArrayList<ArrayList<String>> rightPartitions = partition(right);
for (ArrayList<String> rightPartition : rightPartitions) {
rightPartition.add(0, left);
result.add(rightPartition);
}
}
}
cache.put(s, result);
return cache.get(s);
}
private boolean isPalindrom(String left) {
for (int i = 0; i < left.length() / 2; i++) {
if (left.charAt(i) != left.charAt(left.length() - 1 - i))
return false;
}
return true;
}
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
这题说的不清楚，其实T可以有重复字母，比如AAA，那S中必须包括3个A才行。不是包括A就行了。
自己的做法只能cover木有重复字母的情况。思路： 先把T中的每个字母在S中的位置记录下来，生成一个Map<Char, Queue<Index>>。然后像n个pipe一样，每次找到最小的和最大的head，然后算diff（即包括所有queue head的interval的长度）。用diff update resultLength。最后把最小的那个dequeue，然后新的head和max, min比较，update，都是O(1)的时间。这样是O(n) + O(n)。不过解决不了重复字母的问题。尼玛。。好不容易自己想出来一个。。
下次再想想怎么办，或者干脆看答案。
题目：给一个string，找这个str里面最长的中心对称substring
这个题上来就想一维dp，然后挣扎半天做不出来（找不到一维的d[i]和d[i + 1]的直接关系）。然后上网查答案，原来用二维dp做，而且速度是O(n^2)。其实这题上来就应该先想暴力，然后知道暴力的速度是n^3，然后想办法降一维，别上来就强迫自己O(n)！
二维dp:
- d[i][j]是个boolean，表示(i, j)这个substring是不是中心对称。
- d[i][j]
- 正常情况下，d[i][j] = true when 1.A[i]==A[j] 2. d[i + 1][j – 1] == true (中间那部分已经中心对称了)
- 处理i+1, j-1出界和左边反而大于右边的情况：
- 当i == j时，d[i][j] = 1（一个字母肯定是中心对称）
- 当i == j – 1时，说明两个字符是连着的，看A[i]是否==A[j]就行
- 这个题的坑爹之处在于正常i从0~last, j从0~last那么循环不行。因为d[i][j]用到了d[i + 1][j – 1]，说明i要从后往前，j则要从前往后。导致二层循环是这种顺序：
for (int i = last; i >= 0; i–)
for(int j = i; j <= last; j++)
因为这事想了半天，有点焦躁。
不用二维数组的算法（直接按中心对称的定义来，而不是每个pair算一遍，可以省一维空间）：
- 以每个元素以及间隔为中心（共2 * n – 1个），以相同的速度往两侧扩张，直到两边儿的值不相等了，说明palindrome在此打破，于是输出。这样每次输出的肯定是以当前这个点为中心最长的palindrome）
- 这样过一遍数组，最长的就出来了。
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String odd = expand(s, i, i);
String even = expand(s, i, i + 1);
String longer = odd.length() > even.length() ? odd : even;
res = longer.length() > res.length() ? longer : res;
}
return res;
}
private String expand(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return s.substring(i + 1, j);
}
卧槽这道还真自己做出来了。感觉是二维DP，尽管没让求什么最大最小个数之类的，只是boolean，但是递推关系还是有的。其实只要把状态敢于定义出来（旁边标注物理意义），状态转移方程就能写出来了。然后就是处理最开始。思路：
- 一开始是这么定义的：d[i][j]: whether s1[0, i]的substring和s2[0, j]的substring能够cross match s3[0, i + j + 1]这个substring。比如ab和c，即(0, 1), (0, 0)，能否合起来是acb(0, 2)。要点是s3的index要+1，这个一开始就想错了直接i + j的。
- d[i][j] = s3[i + j + 1] == s2[j] && d[i][j – 1] == true （用第s2的j个来填s3的i + j + 1个能成功）， OR s3[i + j + 1] == s1[i] && d[i – 1][j] == true （用第s1的i个来填s3的i + j + 1个能成功）
- d[i][j]物理意义一定要搞清楚，因为d[0][0]说明拿了两个元素，那么它对应的是长度为2的s3，这index干脆就乱套了。这个时候，换一种方式定义：d[0][0]表示从s1中拿0个，s2中拿0个，然后组成s3（长度为0 + 0)能不能成。这个肯定是true。d[1][0]就能表达只从s1中拿一个，s2中不拿，然后组成长度为1的s3这种make sense的意义了。这样i, j就要一直到=size这么大。所以之前的i + j + 1改成i + j – 1，才能真的往string里charAt。
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;
boolean[][] d = new boolean[s1.length() + 1][s2.length() + 1];
d[0][0] = true;
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (j > 0 && s3.charAt(i + j - 1) == s2.charAt(j - 1) && d[i][j - 1])
d[i][j] = true;
else if (i > 0 && s3.charAt(i + j - 1) == s1.charAt(i - 1) && d[i - 1][j])
d[i][j] = true;
}
}
return d[s1.length()][s2.length()];
}
[leetcode] Edit Distance | 一个string转成另一个string最少要几次operation(增加、删除或者替换一个字符）
Posted on: July 16, 2013
将一个字符串变成另外一个字符串所用的最少操作数，每次只能增加、删除或者替换一个字符。如lamb -> slave
这是经典二维DP题。希望做完这个能掌握二维dp要领，因为实在是不够直观。
思路
- 状态：d[i][j]表示将A的0~i这个substring转化成b的0~j这个substring要的最少次数。
- 所以在二维递归的时候，我们一直有三个已经算好的值：（假设 i = m, j = v，即想算lam->slav)
- d[i-1][j-1]: A, B不算当前char，把A转成B最少要几步 (la -> sla)
- d[i-1][j]: A不算当前char，转成B最少要几步 (la -> slav)
- d[i][j – 1]: A转成B比当前char少一个，最少要几步 (lam -> sla)
- 这样的话，怎么由介三个推d[i][j]呢？
- (la -> sla)已经算好了，所以看m和v是不是同一个字符，是的话，直接d[i][j]就=d[i-1][j-1]；不是的话，相当于替换第m成v，lam就能变成slav了，即步数+1。
- (la -> slav)已经算好，所以现在处理lam怎么办呢？删一个m成la就行了，因为已经知道怎么把la变成slav了。即步数+1。
- (lam -> sla)已经算好，所以后面加一个v就行了，lamv就能变成slav了，即步数+1。
- 二维dp一定要先写出来已经有什么了，并且有的这三个东西的物理意义。这种求最小的，肯定是dp的，就别花时间自我怀疑了。
int minDistance(String word1, String word2) {
int[][] d = new int[word1.length()][word2.length()];
boolean hadSameInA = false;
boolean hadSameInB = false;
if (word1.charAt(0) == word2.charAt(0)) {
d[0][0] = 0;
hadSameInA = true;
hadSameInB = true;
} else {
d[0][0] = 1;
}
//do the same for string B. 但是别人做的都是直接assign i,不考虑有相同的情况。那是怎么回事？
for (int i = 1; i < word1.length(); i++) {
for (int j = 1; j < word2.length(); j++) {
if (word1.charAt(i) == word2.charAt(j))
d[i][j] = d[i - 1][j - 1];
else {
d[i][j] = Math.min(d[i - 1][j - 1] + 1, Math.min(d[i][j - 1] + 1, d[i - 1][j] + 1));
}
return d[word1.length - 1][word2.length - 1];
Lexi's Leetcode solutions 