Back>
In order to search the "needle" in "a big haystack needing to exam, that contains a needle, but hard to see with bare eyes", we can start at the beginning of the haystack. We keeps one pointer i in the haystack (N characters) and another pointer j in the needle (M characters). For each i, it set j = 0, then increase j until find a match or reach the end of the haystack (N - M).
Brute Force approach is the default implementation of java String's contains() method.
In the best scenario, the "needle" is located at the beginning of the haystack, we found it in M compares. In the worst scenario, the "needle" is located at the end of the haystack or not in the haystack at all, we have to do NM compares. On average, the needle is found in the middle, the cost is 1.1N. The extra space needed is 2 pointers i and j, so the space complexity is O(1).
BruteForce.java
