Easy to understand Solution by Boyer-Moore


  • 0
    L
    public class Solution {
        public int strStr(String haystack, String needle) {
            int neeLen = needle.length();
            int hayLen = haystack.length();
            int skip;
            
            //pre-compute
            //right is the hash for all element of needle, store its index, otherwise, it store -1
            int[] right = new int[256];
            for (int c = 0; c < 256; c++) {
                right[c] = -1;
            }
            for (int i = 0; i < neeLen; i++) {
                right[needle.charAt(i)] = i;
            }
            
            for (int i = 0; i <= hayLen - neeLen; i += skip) {
                skip = 0;
                //each loop we find there is no match, we get the index in right, and get the skip that we need to jump for the second time
                for (int j = neeLen - 1; j >= 0; j--) {
                    if (needle.charAt(j) != haystack.charAt(i+j)) {
                        //make sure we move 1 step
                        skip = Math.max(1, j - right[haystack.charAt(i+j)]);
                        break;
                    }
                }
                if (skip == 0) return i;
            }
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.