php - 对齐字符串算法

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开， visit the help center寻求指导。

关闭 10年前.

刚刚完成了一次工作面试，我被要求用这个签名实现一个函数:

function justify($str_in, $desired_length)

它需要模仿 HTML 的 text-align: justify 会做什么，这里有一些例子 (desired_length = 48)

    hello world there ok then                              = hello......world......there.......ok.......then    hello                                                  = .....................hello.....................    ok then                                                = ok.........................................then    this string is almost certainly longer than 48 I think = this.string.is.almost.certainly.longer.than.48.    two words                                              = two.......................................words    three ok words                                         = three.................ok..................words    1 2 3 4 5 6 7 8 9                                      = 1....2....3.....4.....5.....6.....7.....8.....9

(我用句号代替了空格来说明)

单词之间的空格长度不能相差超过一。

我写了一个 PHP 解决方案，但我更感兴趣的是人们可以想出什么算法来解决这个问题。这是我在工作面试中遇到的第一个白板问题，我担心多种因素的综合作用让我花的时间比我应该做的要长。

Answer 1

这是我想出的。我添加了可选的 $char 参数，这样您就可以看到它输出的内容 - 当然您可以将它拉到函数中，以便原型(prototype)符合要求。

function justify($str_in, $desired_length, $char = '_') {

    // Some common vars and simple error checking / sanitation
    $return = '';
    $str_in = trim( $str_in);
    $desired_length = intval( $desired_length);

    // If we've got invalid input, we're done
    if( $desired_length <= 0)
        return $str_in;

    // If the input string is greater than the length, we need to truncate it WITHOUT splitting words
    if( strlen( $str_in) > $desired_length) {
        $str = wordwrap($str_in, $desired_length);
        $str = explode("\n", $str);
        $str_in = $str[0];
    }

    $words = explode( ' ', $str_in);
    $num_words = count( $words);

    // If there's only one word, it's a simple edge case
    if( $num_words == 1) {
        $length = ($desired_length - strlen( $words[0])) / 2;
        $return .= str_repeat( $char, floor( $length)) . $words[0] . str_repeat( $char, ceil( $length));
    } else {
        $word_length = strlen( implode( '', $words));

        // Calculate the number of spaces to distribute over the words
        $num_words--; // We're going to eliminate the last word
        $spaces = floor( ($desired_length - $word_length) / $num_words);
        $remainder = $desired_length - $word_length - ($num_words * $spaces);

        $last = array_pop( $words);
        foreach( $words as $word) {
            // If we didn't get an even number of spaces to distribute, just tack it on to the front
            $spaces_to_add = $spaces;
            if( $remainder > 0) {
                $spaces_to_add++;
                $remainder--;
            }

            $return .= $word . str_repeat( $char, $spaces_to_add);
        }
        $return .= $last;
    }
    return $return;
}

和测试用例:

$inputs = array( 
    'hello world there ok then',
    'hello',
    'ok then',
    'this string is almost certainly longer than 48 I think',
    'two words',
    'three ok words',
    '1 2 3 4 5 6 7 8 9'
);

foreach( $inputs as $x) {
    $ret = justify( $x, 48);
    echo 'Inp: ' . $x . " - strlen(" . strlen( $x) .  ")\n";
    echo 'Out: ' . $ret . " - strlen(" . strlen( $ret) .  ")\n\n";
}

输出:

Inp: hello world there ok then - strlen(25)
Out: hello_______world_______there_______ok______then - strlen(48)

Inp: hello - strlen(5)
Out: _____________________hello______________________ - strlen(48)

Inp: ok then - strlen(7)
Out: ok__________________________________________then - strlen(48)

Inp: this string is almost certainly longer than 48 I think - strlen(54)
Out: this_string_is_almost_certainly_longer_than_48_I - strlen(48)

Inp: two words - strlen(9)
Out: two________________________________________words - strlen(48)

Inp: three ok words - strlen(14)
Out: three__________________ok__________________words - strlen(48)

Inp: 1 2 3 4 5 6 7 8 9 - strlen(17)
Out: 1_____2_____3_____4_____5_____6_____7_____8____9 - strlen(48)

And a demo!

编辑:清理代码，it still works :) .