uopspop

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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×