Archive for September 30th, 2013
这个和regex的 .*不一样。这个是平时cd src*这种；?可以match任意一个字符，*可以match任意一个字符串，可以是空。
算法：下面这个算法超时，不过能写出来就不错了。每次两个字符串的第一个字母比较，若p的第一个字母是*，则一点点的chop s和p除了*剩下的recursive比较。p的那个*可以占用s的0个字符，1个字符，2个字符。。
一点优化：出现连续的*，取最右边那个就行。
public boolean isMatch(String s, String p) {
if (s.length() == 0 && p.length() == 0)
return true;
if (p.length() == 0)
return false;
char c = p.charAt(0);
if (s.length() != 0 && (c == '?' || c == s.charAt(0)))
return isMatch(s.substring(1), p.substring(1));
if (c == '*') {
for (int i = 0; i <= s.length(); i++) {
// i is "* is taking up how many chars in s"
String sLeft = "";
if (s.length() != 0)
sLeft = s.substring(i);
if (isMatch(sLeft, p.substring(1)))
return true;
}
}
return false;
}
Tags: math
这题正经做了一段时间；首先自己想的算法不好，不够数学；另外这个题的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();
}
Lexi's Leetcode solutions 