JIYIK CN >

This article shares with you the application of a small algorithm - finding the common prefix of a string array:

array(
   'abcdefg',
   'abcdfio',
   'abcdqle'
)

In the above array string, the common prefix is ​​'abcd'.

The first thing that comes to mind is to start from the first character of the first string and compare it with the characters of other strings in turn. If they are all equal, we save them until one is not equal, then we end the subsequent comparison.

The code is as follows

function commonPrefix($arr){
    $count = strlen($arr[0]);
    $prefix = '';
    for($i=0;$i<$count;$i++){
        $char = $arr[0][$i];
        $flag = true;
        foreach($arr as $val){
            if($char != $val[$i]){
                $flag = false;
                break;
            }
        }
        if(!$flag) break;
        $prefix .= $char;
    }
    return $prefix;
}

This code works great for finding the common prefix of the above array of strings.

But there is a serious bug in the above program. When the length of some strings in the array is smaller than the length of the first string, an error may occur. Let's look at the following array:

array(
  'abcde',
  'abc',
  'abcrhgh',
  'abcdfg',
  'abcfg'
);

We can see from the array above that the common prefix is ​​abc. During the comparison process, when comparing the fourth character d, we check whether the second string has only three characters. Therefore, $arr[1][3] does not have this variable. Therefore, an error is reported.

There are two solutions to this situation

Method 1: Before each comparison, determine whether the variable exists. If it does not exist, terminate the subsequent comparison directly.

Some of the code is as follows:

foreach($arr as $val){
   if(!isset($val[$i]){
            $flag = false;
            break;
   }
   if($char != $val[$i]){
       $flag = false;
       break;
   }
}

Method 2: Before searching and comparing, find out the length of the shortest string in the array and use this length as the termination condition of the loop.

The code is as follows:

function commonPrefix($arr){
         $count = strlen($arr[0]);
for($i = 0;$i<count($arr);$i++){
    if(strlen($arr[$i]) <= $count){
        $count = strlen($arr[$i]);
    }
}
    $prefix = '';
    for($i=0;$i<$count;$i++){
        $char = $arr[0][$i];
        $flag = true;
        foreach($arr as $val){
            if($char != $val[$i]){
                $flag = false;
                break;
            }
        }
        if(!$flag) break;
        $prefix .= $char;
    }
    return $prefix;
}

The above is the code for finding common prefixes in a string array. I hope it will be helpful to you.