Archive for August 25th, 2013
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) == '.';
}
[design pattern] Observer Pattern
Posted on: August 25, 2013
花一个小时看完了书，自己写了一遍，基本明白咋回事了。需要两个接口，Source and Listener（我自己瞎起的名字），Source是那个变的，Listener是那个被通知的。
- Source:
- 一个private List<Listener> listeners;
- 一个registerListener(Listener l)函数，把l加到listeners里面去
- 一个removeListener(Listener l)函数，把l从listeners里面删掉
- 一个notifyAllListeners()函数，里面对于每个listener, call listener的update()。不需要加parameter，只是通知list里面的监听者“有东西改了”， 具体改的是啥，让Listener里面的update函数自己从source reference里面pull去。
- Listener:
- 一个private Source s
- 一个constructor that takes a Source obj, 初始的时候就把“听谁”（source）给联系上。
- 一个update()函数，里面把Source s cast成自己真监听的concrete type（比如“杂志”），然后从这个s里面pull data。
重点：
- Source的notify函数只是负责告诉listeners，有变动了，你们来pull我的data吧。不用真把动的是哪个data传过去。当然也可以pass一个para说明到底是哪个data变了，client好知道具体pull哪个data。
- Listener的update()函数只被source的notify叫，然后函数里面取出当前obj的source reference, cast, pull data and use it.
- Register这些东西都是在main函数里叫的。
public class Magazine implements Source {
private List<Listner> subscribers;
private String editorName;
public String getEditorName() {
return editorName;
}
public Magazine () {
this.subscribers = new ArrayList<Listner>();
this.editorName = "Christina";
}
public void changeEditorName(String newEditor) {
this.editorName = newEditor;
notifyListners();
}
@Override
public void registerListner(Listner l) {
subscribers.add(l);
}
@Override
public void removeListner(Listner l) {
if (subscribers.contains(l))
subscribers.remove(l);
}
@Override
public void notifyListners() {
for (Listner subscriber : subscribers) {
subscriber.update();
}
}
public static void main(String[] args) {
Magazine m = new Magazine();
Subscriber sub1 = new Subscriber(m, "sub1");
Subscriber sub2 = new Subscriber(m, "sub2");
m.registerListner(sub1);
m.registerListner(sub2);
m.changeEditorName("Meredith");
m.removeListner(sub2);
m.changeEditorName("Alex");
}
}
public class Subscriber implements Listner {
private Source magazine;
private String name;
private String currentEditorName;
public Subscriber(Source s, String name) {//this is how one listner bind to one subject.
this.name = name;
this.magazine = s;
}
@Override
public void update() {
//each subscriber knows the subject is a magazine, so it can cast it's subject to magazine and use this subject's properties.
String newEditor = ((Magazine) this.magazine).getEditorName();
this.currentEditorName = newEditor;
System.out.println(name + ": Updating editor name to " + newEditor);
}
Lexi's Leetcode solutions 