McGar
BAN USERpublic ArrayList<ArrayList<Integer>> kMemberSubsetsWithDup(int[] a, int k){
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
//ArrayList<Integer> empty = new ArrayList<Integer>();
//list.add(empty);
if(a == null || a.length < k){
return list;
}
Arrays.sort(a);
subsets(list, a, new ArrayList<Integer>(), 0, k);
return list;
}
public void subsets(ArrayList<ArrayList<Integer>> list, int[] a,
ArrayList<Integer> cur, int start, int k){
if(cur.size() == k){
list.add(cur);
}
for(int i = start; i < a.length; i++){
cur.add(a[i]);
subsets(list, a, new ArrayList<Integer>(cur), i+1, k);
cur.remove(cur.size() - 1);
while(i + 1 < a.length && a[i] == a[i+1]){
i++;
}
}
}
//s is input string, p is pattern
public boolean isMatch(String s, String p){
if(s == null || p == null){
return s == null && p == null;
}
if(p.length() == 0){
return s.length() == 0;
}
if(p.length() == 1 || (p.charAt(1) != '*' && p.charAt(1) != '+')){
if(s.length() == 0 || s.charAt(0) != p.charAt(0)){
return false;
}
return isMatch(s.substring(1), p.substring(1));
}else if(p.charAt(1) == '*'){
int index = -1;
while(index < s.length() &&(index < 0 || s.charAt(index) == p.charAt(0))){
if(isMatch(s.substring(index+1), p.substring(2))){
return true;
}
index++;
}
return false;
}else{
return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p.substring(2));
}
}
- McGar April 09, 2014
- McGar April 09, 2014