# Untitled

Sep 5th, 2020 (edited)
1,493
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. // main concept: convert substring into a num, so we can calculate each round without inner loop
3. //
4. // what I learned:
5. // * leverage hash function (magicNum = 31)
6. // * Math.pow -> leverage binary multiplication concept (cool)
7. class Solution {
8.     public int strStr(String haystack, String needle) {
9.         if (null == haystack) return -1;
10.         if (null == needle) return -1;
11.         if (needle.isEmpty()) return 0; // if empty string, return 0
12.         if (haystack.length() < needle.length()) return -1;
13.
14.         int magicNum = 31; // for hashing
15.         // int base = 1000000; // if num too big, you need this to %
16.
17.         // get multiply num for later use (represent the first char of each-round substring)
18.         int power = 1;
19.         for (int k = 0 ; k < needle.length() - 1; k++) { // attention: you only need length() - 1 multiplations
20.             power = power * magicNum;
21.         }
22.
23.         // get target case:
24.         int targetHashNum = 0;
25.         for (int n = 0; n < needle.length(); n++) {
26.             targetHashNum = targetHashNum * magicNum + needle.charAt(n); // for loop AND * magicNum ==> Math.pow() //
27.                                                                  // like what we do for binary * 2, move left
28.         }
29.
30.         // get base case
31.         int nowHashNum = 0;
32.         for (int i = 0; i < needle.length(); i++) {
33.             nowHashNum = nowHashNum * magicNum + haystack.charAt(i); // for-loop AND * magicNum ==> Math.pow()
34.                                                              // however, Math.pow(): Double force us to deal
35.                                                              // with type conversion
36.         }
37.
38.         // main code
39.         for (int i = 0; i <= haystack.length() - needle.length(); i++) {
40.             if (i != 0) { // skip base case
41.                 // abc - a
42.                 nowHashNum = nowHashNum - ( haystack.charAt(i-1) * power);
43.
44.                 // bc + d
45.                 nowHashNum = (nowHashNum * magicNum); // move left
46.                 nowHashNum = nowHashNum + haystack.charAt(i+needle.length()-1); // + d
47.             }
48.
49.             // 1st layer check: hashing
50.             if (nowHashNum == targetHashNum) {
51.                 // 2nd layer check: cuz hash, we still have to make sure, it is actually the same
52.                 if (haystack.substring(i, i+needle.length()).equals(needle)) {
53.                     return i;
54.                 }
55.             }
56.
57.         }
58.
59.         return -1;
60.     }
61.
62. };
RAW Paste Data