2
\$\begingroup\$
function min_strpos_array($haystack, $needles) {
    $min = null;
    for ($i = 0; $i < count($needles); $i++) {
        $strpos = strpos($haystack, $needles[$i]);
        if ($strpos !== FALSE) {
            $min = $strpos;
            for ($i = $i + 1; $i < count($needles); $i++) {
                $strpos = strpos($haystack, $needles[$i]);
                if ($strpos !== FALSE) {
                    $min = $min < $strpos ? $min : $strpos;
                }
            }
        }
    }
    return $min;
}

echo min_strpos_array('hello#,?', array('#', '?')); //5
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Well, any time you have nested for loops, you should cringe a little because it means you're running in O(n^2) time. Sometimes it's unavoidable, but often you can do something to bring it down significantly. Edit: this algorithm is actually O(n).

In your case, you can reduce your algorithm to O(n), which is a huge performance boost.

Here are your new steps:

Loop through each needle
    Get the position of the needle in the haystack
    If the position is less than our current minimum:
        Set the minimum to the position of the needle

Basically, we find the first minimum and then overwrite it as each new minimum is found.

Here is my version of your code:

function min_strpos_array($haystack, $needles){
    $length = count($needles);
    $min = strlen($haystack) + 1;
    for($i = 0; $i < $length; $i++){
        $strpos = strpos($haystack, $needles[$i]);
        if ($strpos !== FALSE){
            if($strpos < $min){
                $min = $strpos;
            }
        }
    }
    return $min;
}

echo min_strpos_array('hello#,?', array('#', '?')); //5

Outside of the algorithm, I made a few other changes.

for ($i; $i < count($needles); $i++) became for ($i = 0; $i < $length; $i++). When you have a function in a for loop, it gets called every iteration, which is unnecessary when the value doesn't change. Just get the number of needles outside the loop and reference that. You could also use a foreach loop, but I'm not familiar enough with PHP to definitively say that it's better.

$min = null; became $min = strlen($haystack) + 1;. This ensures that if our needle exists in the haystack, we can compare the position with our minimum. It also has the side effect of returning strlen($haystack) + 1 if none of the needles are found in the haystack, which may or may not be desirable. If you don't like that, just add an if statement before you return.

You really don't need to nest your if statements like you did either, but I decided to leave those in in case you chose to so intentionally.

Two important things to take away from this:

  1. Watch out for nested for loops. Pretend they're screaming at you to find a better algorithm.
  2. Don't call functions in the argument of a for loop unless you need to get a value that might change during the loop.
\$\endgroup\$
2
  • \$\begingroup\$ The running time is not O(n^2) because the second loop continues from where the first loop stopped. I want to return null if any needle not found so as you said I must add if ($min === strlen($haystack) + 1) { return null; } which I think its more complex than having extra loop. And yes you was right about calculating the length outside of the loop. \$\endgroup\$
    – Almis
    Jun 2, 2014 at 21:47
  • \$\begingroup\$ Yeah, you are right. I didn't notice that you weren't resetting the loop. Still, this solution is better because it solves the problem directly instead of hacking together another for loop. And you shouldn't be afraid of an if statement. \$\endgroup\$
    – Meredith
    Jun 2, 2014 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.