## Monday, January 25, 2016

### 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  }```

``` 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++) {
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）
F面经prepare：strstr变种