F面经prepare:strstr变种
F面经prepare:strstr变种
* Given an integer k>=1 and two strings A and B (length ~n each); * Figure out if there is any common substring of length at least k. * (i.e. any string of length at least k, that is a substring of both A and B) * * A="facebook", B="bookshelf", k=3 ==> true ^^^ ^^^ * A="facebook", B="bookshelf", k=4 ==> true ^^^^ ^^^^ * A="facebook", B="bookshelf", k=5 ==> false
1 public boolean check(String A, String B, int k) { 2 3 int lenA = A.length(); 4 int lenB = B.length(); 5 for (int i=0; i<=lenA-k; i++) { 6 String stra = A.substring(i, i+k); 7 for (int j=0; j<=lenB-k; j++) { 8 String strb = B.substring(j,j+k); 9 if (stra.equals(strb)) return true; 10 } 11 } 12 return false; 13 }
follow up: How to optimize?
想到KMP了,trie了,居然没有想到HashSet,然后KMP和trie的时间复杂度又没有搞太对
他们真的很喜欢问时间复杂度,空间复杂度,时间换空间,空间换时间
1 public boolean check(String A, String B, int k) { 2 //store B's substring of length k to hashSet 3 HashSet<String> set = new HashSet<String>(); 4 for (int i=0; i<B.length()-k; i++) { 5 set.add(B.substring(i, i+k)); 6 } 7 for (int i=0; i<A.length()-k; i++) { 8 String sbstra = A.substring(i, i+k); // don't use substring 9 if (B.contains(sbstra)) return true; 10 } 11 return false; 12 }
这道题一点都不难,只是
1.受以前思维定式影响
2. 考场真的是思路就很局限, 放不开
3. 这道题面经还见过,别人提到过set,没细看,恰好这个方法忘记了
4. 考场写的时候,真的是连for(int i=0; i<=A.length()-k; i++) 这个是不是A.length()-k都想不清楚
应对:
1.重视面经。看过做过会占很大便宜
2. 要加强时间复杂度,空间复杂度训练
3. 要加强思维敏捷度训练
4. 写code能力(比如这次A.length()-k)