对齐字符串算法 [英] Justify string algorithm

问题描述

只是进行一次面试，要求我使用此签名来实现一项功能:

Just tanked a job interview where I was asked to implement a function with this signature:

function justify($str_in, $desired_length)

它需要模仿HTML的文本对齐方式:justify会做的，这是一些示例(desired_length = 48)

It needs to mimic what HTML's text-align: justify would do, here's some examples (desired_length = 48)

你好，世界好吧，然后=你好……世界……那里…….好…….然后你好= .....................你好.....................好的然后=好的............................................然后这个字符串几乎肯定比48长，我认为= this.string.is.almost.certainly.longer.than.48.两个字=两个..........................................字三个确定的单词=三个........确定..................单词1 2 3 4 5 6 7 8 9 = 1..2 .... 3 ... 4 .... 5..6 ..... 7 .....8 ..... 9 

    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


(我用句号代替了空格以说明)
(I replaced the spaces with periods to illustrate)
单词之间的空格长度不得相差超过一个.
The length of spaces between words may never differ by more than one.
我已经编写了一个PHP解决方案，但是我对人们可以提出什么样的算法来解决该问题更感兴趣.这是有史以来我在工作面试中遇到的第一个白板问题，我担心多种因素使我的工作时间超出了应有的时间.
I have written a PHP solution, but I am more interested in what algorithms people can come up with to solve the problem. It was my first whiteboard question at a job interview ever, and I'm afraid a combination of factors made me take way longer than I should have.
推荐答案
这就是我想出的.我添加了可选的 $ char 参数，因此您可以看到它的输出-当然，您可以将其拉入函数中，以便原型满足要求.
Here's what I came up with. I added the optional $char parameter so you can see what it's outputting - Of course you can pull it inside the function so the prototype matches the requirement.
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)

 还有一个演示！ 
 :清理了代码，并且它仍然有效:).
 Cleaned up the code, and it still works :).

                        
这篇关于对齐字符串算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！