Lexi's Leetcode solutions

Posts Tagged ‘string

比如abcdefg, defmnabs,最长公共subtring是def。

又是二维DP求String的最优解。居然还是算法课作业做过,真是一点印象也木有了。

  • d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
  • d[i][j] =
    1. A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
    2. 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]的某个比较方式的最优解
Advertisements

这是好难好难的二维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,那么
      1. 可以把RABB的第二个B删除得到RAB,所以d[i][j]最少也是d[i – 1][j]
      2. 可以用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
  1. 第一行和最后一行每个zigzag段只要append一个就行了
  2. 中间那些行每次要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();
}
Tags: , ,

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:

example: aabc matches c*a*b.

思路:

  1. 两个指针i, j,i指regular expression,j指真的string。
  2. 观察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]..
      1. 先试试“用0个p[i]“,即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了,直接返回true,不成功,接着做第二步。
      2. 从“用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) == '.';
}
Tags: , ,

这应该是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)。不过解决不了重复字母的问题。尼玛。。好不容易自己想出来一个。。

下次再想想怎么办,或者干脆看答案。

Tags: ,