alignmentstringalgorithm
只是在求职面试中，我被要求用这个签名来实现一个function：
function justify($str_in, $desired_length) 它需要模仿HTML的text-align：justify会做什么，这里有一些例子（desired_length = 48）
hello world there ok then = hello ...... world ...... there ........好的.......然后
你好........................你好.....................
好吧然后=好.........................................然后
这个string几乎肯定比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
（我用句点replace了空格来说明）
单词之间的空格长度可能永远不会相差一个以上。
我已经写了一个PHP解决scheme，但我更感兴趣的是人们可以想出什么algorithm来解决这个问题。 这是我有史以来第一次接受面试的白板问题，恐怕有一些因素让我走的时间比我应该做的还要长。
这是我想出来的。 我添加了可选的$char参数，所以你可以看到它的输出 – 当然，你可以把它拉到函数内，使原型符合要求。
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; }
而testing案例：
$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)
和一个演示！
编辑：清理代码， 它仍然工作:) 。
使它成为个人的挑战，不要使用任何循环/recursion或带callback的正则expression式。 我用一个explode()和一个单一的implode()来实现这一点。 巨大的成功！
代码
function justify($str, $maxlen) { $str = trim($str); $strlen = strlen($str); if ($strlen >= $maxlen) { $str = wordwrap($str, $maxlen); $str = explode("\n", $str); $str = $str[0]; $strlen = strlen($str); } $space_count = substr_count($str, ' '); if ($space_count === 0) { return str_pad($str, $maxlen, ' ', STR_PAD_BOTH); } $extra_spaces_needed = $maxlen - $strlen; $total_spaces = $extra_spaces_needed + $space_count; $space_string_avg_length = $total_spaces / $space_count; $short_string_multiplier = floor($space_string_avg_length); $long_string_multiplier = ceil($space_string_avg_length); $short_fill_string = str_repeat(' ', $short_string_multiplier); $long_fill_string = str_repeat(' ', $long_string_multiplier); $limit = ($space_string_avg_length - $short_string_multiplier) * $space_count; $words_split_by_long = explode(' ', $str, $limit+1); $words_split_by_short = $words_split_by_long[$limit]; $words_split_by_short = str_replace(' ', $short_fill_string, $words_split_by_short); $words_split_by_long[$limit] = $words_split_by_short; $result = implode($long_fill_string, $words_split_by_long); return $result; }
短（348字）
function j($s,$m){$s=trim($s);$l=strlen($s);if($l>=$m){$s=explode("\n",wordwrap($s,$m));$s=$s[0];$l=strlen($s);}$c=substr_count($s,' ');if($c===0)return str_pad($s,$m,' ',STR_PAD_BOTH);$a=($m-$l+$c)/$c;$h=floor($a);$i=($a-$h)*$c;$w=explode(' ',$s,$i+1);$w[$i]=str_replace(' ',str_repeat(' ',$h),$w[$i]);return implode(str_repeat(' ',ceil($a)),$w);}
algorithm/代码解释
- 处理两个例外（string长于最大长度或只有一个字）。
- 找出每个单词之间所需的平均空间（
$space_string_avg_length）。 - 根据
$space_string_avg_lengthceil()和floor()分别在单词之间创build一个长短填充string。 - 找出我们需要多less长填充string。 （
$limit+1）。 - 根据我们需要多长的填充string分割文本。
- 使用短填充stringreplace数组的最后一部分中的空格。
- 连同长填充string一起join拆分文本。
testing
$tests = 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 ($tests as $test) { $len_before = strlen($test); $processed = str_replace(' ', '_', justify($test, 48)); $len_after = strlen($processed); echo "IN($len_before): $test\n"; echo "OUT($len_after): $processed\n"; }
结果
IN(25): hello world there ok then OUT(48): hello_______world_______there_______ok______then IN(5): hello OUT(48): _____________________hello______________________ IN(7): ok then OUT(48): ok__________________________________________then IN(54): this string is almost certainly longer than 48 I think OUT(48): this_string_is_almost_certainly_longer_than_48_I IN(9): two words OUT(48): two________________________________________words IN(14): three ok words OUT(48): three__________________ok__________________words IN(17): 1 2 3 4 5 6 7 8 9 OUT(48): 1_____2_____3_____4_____5_____6_____7_____8____9
看到它运行！
这是我的解决scheme，没有讨厌的循环
function justify( $str_in, $desired_length=48 ) { if ( strlen( $str_in ) > $desired_length ) { $str_in = current( explode( "\n", wordwrap( $str_in, $desired_length ) ) ); } $string_length = strlen( $str_in ); $spaces_count = substr_count( $str_in, ' ' ); $needed_spaces_count = $desired_length - $string_length + $spaces_count; if ( $spaces_count === 0 ) { return str_pad( $str_in, $desired_length, ' ', STR_PAD_BOTH ); } $spaces_per_space = ceil( $needed_spaces_count / $spaces_count ); $spaced_string = preg_replace( '~\s+~', str_repeat( ' ', $spaces_per_space ), $str_in ); return preg_replace_callback( sprintf( '~\s{%s}~', $spaces_per_space ), function ( $m ) use( $spaces_per_space ) { return str_repeat( ' ', $spaces_per_space-1 ); }, $spaced_string, strlen( $spaced_string ) - $desired_length ); }
评论和输出…
https://gist.github.com/2939068
- 找出有多less空间
- 找出需要多less空间
- 将现有空间replace为满足或仅超过所需线路长度所需的空间量（均匀分布）
- 使用preg_replace_callback用
\s{spaces_inserted-1}replace\s{spaces_inserted}的数量以满足所需的行长度
我想看看哪个algorithm是最有效的，所以我跑了一些基准。 我做了所有7个testing用例的100k次迭代。 （在单核Ubuntu VM中运行）
@ppsreejith和@Kristian Antonsen的代码的结果被省略了，因为他们的代码在我尝试运行时崩溃了。 @PhpMyCoder的代码运行，只要我没有做对象构build后的长度为48的长度。 所以testing结果不完整。 （固定）
基准testing结果
$ php justify.bench.php 盖伦（justify1）：5.1464750766754 nickb（justify2）：3.8629620075226 Paolo Bergantino（justify3）：4.3705048561096 user381521（justify5）：8.5988481044769 vlzvl（justify7）：6.6795041561127 亚历山大（justify8）：6.7060301303864 ohaal（justify9）：2.9896130561829 PhpMyCoder：6.1514630317688（修正！）
justify.bench.php
<?php $tests = 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' ); $testers = array( 'Galen' => 'justify1', 'nickb' => 'justify2', 'Paolo Bergantino' => 'justify3', // 'Kristian Antonsen' => 'justify4', 'user381521' => 'justify5', // 'ppsreejith' => 'justify6', 'vlzvl' => 'justify7', 'Alexander' => 'justify8', 'ohaal' => 'justify9' ); // ppsreejith and Kristian Antonsen's code crashed and burned when I tried to run it // PhpMyCoder is a special case, but his code also crashed when doing $jus->format(48); foreach ($testers as $tester => $func) { $b=microtime(true); for($i=0;$i<100000;$i++) foreach ($tests as $test) $func($test,48); $a=microtime(true); echo $tester.'('.$func.'): '.($a-$b)."\n"; } echo "\n"; // Fixed! $jus = new Justifier($tests); $b=microtime(true); for($i=0;$i<100000;$i++) { $jus->format(54); } $a=microtime(true); echo 'PhpMyCoder: '.($a-$b)." (Fixed!)\n"; // ALGORITHMS BELOW // Galen function justify1( $str_in, $desired_length=48 ) { if ( strlen( $str_in ) > $desired_length ) { $str_in = current( explode( "\n", wordwrap( $str_in, $desired_length ) ) ); } $string_length = strlen( $str_in ); $spaces_count = substr_count( $str_in, ' ' ); $needed_spaces_count = $desired_length - $string_length + $spaces_count; if ( $spaces_count === 0 ) { return str_pad( $str_in, $desired_length, ' ', STR_PAD_BOTH ); } $spaces_per_space = ceil( $needed_spaces_count / $spaces_count ); $spaced_string = preg_replace( '~\s+~', str_repeat( ' ', $spaces_per_space ), $str_in ); return preg_replace_callback( sprintf( '~\s{%s}~', $spaces_per_space ), function ( $m ) use( $spaces_per_space ) { return str_repeat( ' ', $spaces_per_space-1 ); }, $spaced_string, strlen( $spaced_string ) - $desired_length ); } // nickb function justify2($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; } // Paolo Bergantino function justify3($str, $to_len) { $str = trim($str); $strlen = strlen($str); if($str == '') return ''; if($strlen >= $to_len) { return substr($str, 0, $to_len); } $words = explode(' ', $str); $word_count = count($words); $space_count = $word_count - 1; if($word_count == 1) { return str_pad($str, $to_len, ' ', STR_PAD_BOTH); } $space = $to_len - $strlen + $space_count; $per_space = $space/$space_count; if(is_int($per_space)) { return implode($words, str_pad('', $per_space, ' ')); } $new_str = ''; $spacing = floor($per_space); $new_str .= $words[0] . str_pad('', $spacing); foreach($words as $x => $word) { if($x == $word_count - 1 || $x == 0) continue; if($x < $word_count - 1) { $diff = $to_len - strlen($new_str) - (strlen(implode('', array_slice($words, $x)))); $new_str .= $word . str_pad('', floor($diff/($space_count - $x)), ' '); } } $new_str .= $words[$x]; return $new_str; } // Kristian Antonsen function justify4($str_in, $desired_length) { foreach ($str_in as &$line) { $words = explode(' ', $line); $word_count = count($words) - 1; $spaces_to_fill = $desired_length - strlen($line) + $word_count; if (count($words) == 1) { $line = str_repeat('_', ceil($spaces_to_fill/2)) . $line . str_repeat('_', floor($spaces_to_fill/2)); continue; } $next_space = floor($spaces_to_fill/$word_count); $leftover_space = $spaces_to_fill % $word_count; $line = array_shift($words); foreach($words as $word) { $extra_space = ($leftover_space) ? ceil($leftover_space / $word_count) : 0; $leftover_space -= $extra_space; $line .= str_repeat('_', $next_space + $extra_space) . $word; } } return $str_in; } // user381521 function justify5 ($str, $len) { // split by whitespace, remove empty strings $words = array_diff (preg_split ('/\s+/', $str), array ("")); // just space if no words if (count ($words) == 0) return str_repeat (" ", $len); // add empty strings if only one element if (count ($words) == 1) $words = array ("", $words[0], ""); // get number of words and spaces $wordcount = count ($words); $numspaces = $wordcount - 1; // get number of non-space characters $numchars = array_sum (array_map ("strlen", $words)); // get number of characters remaining for space $remaining = $len - $numchars; // return if too little spaces remaining if ($remaining <= $numspaces) return substr (implode (" ", $words), 0, $len); // get number of spaces per space $spaces_per_space = $remaining / $numspaces; $spaces_leftover = $remaining % $numspaces; // make array for spaces, spread out leftover spaces $spaces = array_fill (0, $numspaces, $spaces_per_space); while ($spaces_leftover--) $spaces[$numspaces - $spaces_leftover - 1]++; $spaces[] = 0; // make count ($words) == count ($spaces) // join it all together $result = array (); foreach ($words as $k => $v) array_push ($result, $v, str_repeat (" ", $spaces[$k])); return implode ($result); } // ppsreejith function justify6($str, $to_len) { $str = trim($str); $strlen = strlen($str); if($str == '') return ''; if($strlen >= $to_len) { return substr($str, 0, $to_len); } $words = explode(' ', $str); $word_count = count($words); $space_count = $word_count - 1; if($word_count == 1) { return str_pad($str, $to_len, ' ', STR_PAD_BOTH); } $space = $to_len - $strlen + $space_count; $per_space = floor($space/$space_count); $spaces = str_pad('', $per_space, ' '); $curr_word = implode($words, $spaces); while(strlen($curr_word) < $to_len){ $curr_word = substr($curr_word,0,preg_match("[! ][".$spaces."][! ]",$curr_word)." ".preg_match("[! ][".$spaces."][! ]",$curr_word)); } return $curr_word; } // vlzvl function justify7($str_in, $desired_length) { $str_in = preg_replace("!\s+!"," ",$str_in); // get rid of multiple spaces $words = explode(" ",$str_in); // break words $num_words = sizeof($words); // num words if ($num_words==1) { return str_pad($str_in,$desired_length,"_",STR_PAD_BOTH); } else { $num_chars = 0; $lenwords = array(); for($x=0;$x<$num_words;$x++) { $num_chars += $lenwords[$x] = strlen($words[$x]); } $each_div = round(($desired_length - $num_chars) / ($num_words-1)); for($x=0,$sum=0;$x<$num_words;$x++) { $sum += ($lenwords[$x] + ($x<$num_words-1 ? $each_div : 0)); } $space_to_addcut = ($desired_length - $sum); for($x=0;$x<$num_words-1;$x++) { $words[$x] .= str_repeat("_",$each_div+($each_div>1? ($space_to_addcut<0?-1:($space_to_addcut>0?1:0)) :0)); if ($each_div>1) { $space_to_addcut += ($space_to_addcut<0 ? 1 : ($space_to_addcut>0?-1:0) ); } } return substr(implode($words),0,$desired_length); } } // Alexander function justify8($str, $length) { $words = explode(' ', $str); if(count($words)==1) $words = array("", $str, ""); $spaces = $length - array_sum(array_map("strlen", $words)); $add = (int)($spaces / (count($words) - 1)); $left = $spaces % (count($words) - 1); $spaced = implode(str_repeat("_", $add + 1), array_slice($words, 0, $left + 1)); $spaced .= str_repeat("_", max(1, $add)); $spaced .= implode(str_repeat("_", max(1, $add)), array_slice($words, $left + 1)); return substr($spaced, 0, $length); } // ohaal function justify9($s,$m){$s=trim($s);$l=strlen($s);if($l>=$m){$s=explode("\n",wordwrap($s,$m));$s=$s[0];$l=strlen($s);}$c=substr_count($s,' ');if($c===0)return str_pad($s,$m,' ',STR_PAD_BOTH);$a=($m-$l+$c)/$c;$h=floor($a);$i=($a-$h)*$c;$w=explode(' ',$s,$i+1);$w[$i]=str_replace(' ',str_repeat(' ',$h),$w[$i]);return implode(str_repeat(' ',ceil($a)),$w);} // PhpMyCoder class Justifier { private $text; public function __construct($text) { if(!is_string($text) && !is_array($text)) { throw new InvalidArgumentException('Expected a string or an array of strings, instead received type: ' . gettype($text)); } if(is_array($text)) { // String arrays must be converted to JustifierLine arrays $this->text = array_map(function($line) { return JustifierLine::fromText($line); }, $text); } else { // Single line of text input $this->text = $text; } } public function format($width = NULL) { // Strings have to be broken into an array and then jusitifed if(is_string($this->text)) { if($width == null) { throw new InvalidArgumentException('A width must be provided for separation when an un-split string is provided'); } if($width <= 0) { throw new InvalidArgumentException('Expected a positive, non-zero width, instead received width of ' . $width); } // Break up a JustifierLine of all text until each piece is smaller or equal to $width $lines = array(JustifierLine::fromText($this->text)); $count = 0; $newLine = $lines[0]->breakAtColumn($width); while($newLine !== null) { $lines[] = $newLine; $newLine = $lines[++$count]->breakAtColumn($width); } } else { $lines = $this->text; // Allow for fluid width (uses longest line with single space) if($width == NULL) { $width = -1; foreach($lines as $line) { // Width of line = Sum of the lengths of the words and the spaces (number of words - 1) $newWidth = $line->calculateWordsLength() + $line->countWords() - 1; if($newWidth > $width) { // Looking for the longest line $width = $newWidth; } } } } // Justify each element of array //$output = array_map(function($line) use ($width) { // return $this->justify($line, $width); //}, $lines); $output = array(); foreach($lines as $line) { $output[] = $this->justify($line, $width); } // If a single-line is passed in, a single line is returned if(count($output)) { return $output[0]; } return $output; } private function justify(JustifierLine $line, $width) { // Retrieve already calculated line information $words = $line->extractWords(); $spaces = $line->countWords() - 1; $wordLens = $line->findWordLengths(); $wordsLen = $line->calculateWordsLength(); $minWidth = $wordsLen + $spaces; $output = ''; if($minWidth > $width) { throw new LengthException('A minimum width of ' . $minWidth . ' was required, but a width of ' . $width . ' was given instead'); } // No spaces means only one word (center align) if($spaces == 0) { return str_pad($words[0], $width, ' ', STR_PAD_BOTH); } for(;$spaces > 0; $spaces--) { // Add next word to output and subtract its length from counters $output .= array_shift($words); $length = array_shift($wordLens); $wordsLen -= $length; $width -= $length; if($spaces == 1) { // Last Iteration return $output . str_repeat(' ', $width - $wordsLen) . $words[0]; } // Magic padding is really just simple math $padding = floor(($width - $wordsLen) / $spaces); $output .= str_repeat(' ', $padding); $width -= $padding; } } } class JustifierLine { private $words; private $numWords; private $wordLengths; private $wordsLength; public static function fromText($text) { // Split words into an array preg_match_all('/[^ ]+/', $text, $matches, PREG_PATTERN_ORDER); $words = $matches[0]; // Count words $numWords = count($words); // Find the length of each word $wordLengths = array_map('strlen', $words); //And Finally, calculate the total length of all words $wordsLength = array_reduce($wordLengths, function($result, $length) { return $result + $length; }, 0); return new JustifierLine($words, $numWords, $wordLengths, $wordsLength); } private function __construct($words, $numWords, $wordLengths, $wordsLength) { $this->words = $words; $this->numWords = $numWords; $this->wordLengths = $wordLengths; $this->wordsLength = $wordsLength; } public function extractWords() { return $this->words; } public function countWords() { return $this->numWords; } public function findWordLengths() { return $this->wordLengths; } public function calculateWordsLength() { return $this->wordsLength; } public function breakAtColumn($column) { // Avoid extraneous processing if we can determine no breaking can be done if($column >= ($this->wordsLength + $this->numWords - 1)) { return null; } $width = 0; $wordsLength = 0; for($i = 0; $i < $this->numWords; $i++) { // Add width of next word $width += $this->wordLengths[$i]; // If the line is overflowing past required $width if($width > $column) { // Remove overflow at end & create a new object with the overflow $words = array_splice($this->words, $i); $numWords = $this->numWords - $i; $this->numWords = $i; $wordLengths = array_splice($this->wordLengths, $i); $tempWordsLength = $wordsLength; $wordsLength = $this->wordsLength - $wordsLength; $this->wordsLength = $tempWordsLength; return new JustifierLine($words, $numWords, $wordLengths, $wordsLength); } $width++; // Assuming smallest spacing to fit // We also have to keep track of the total $wordsLength $wordsLength += $this->wordLengths[$i]; } return null; } }
这是我的解决scheme。 没有讨厌的正则expression式:)
function justify($str, $length) { $words = explode(' ', $str); if(count($words)==1) $words = array("", $str, ""); $spaces = $length - array_sum(array_map("strlen", $words)); $add = (int)($spaces / (count($words) - 1)); $left = $spaces % (count($words) - 1); $spaced = implode(str_repeat("_", $add + 1), array_slice($words, 0, $left + 1)); $spaced .= str_repeat("_", max(1, $add)); $spaced .= implode(str_repeat("_", max(1, $add)), array_slice($words, $left + 1)); return substr($spaced, 0, $length); }
这由PHParraysfunction提供支持 。
这是一个工作的例子 。
就这样，没有人认为我试图让他们为我做功课，这是我的（工作，我认为）解决scheme。
我不确定我是否有可能按照需求在白板上编写这么多的代码，但是我很想好好看看其他人如何在不看代码的情况下解决这个问题。 （在面试之前，我在面试中已经习惯了这种说法）
function justify($str, $to_len) { $str = trim($str); $strlen = strlen($str); if($str == '') return ''; if($strlen >= $to_len) { return substr($str, 0, $to_len); } $words = explode(' ', $str); $word_count = count($words); $space_count = $word_count - 1; if($word_count == 1) { return str_pad($str, $to_len, ' ', STR_PAD_BOTH); } $space = $to_len - $strlen + $space_count; $per_space = $space/$space_count; if(is_int($per_space)) { return implode($words, str_pad('', $per_space, ' ')); } $new_str = ''; $spacing = floor($per_space); $new_str .= $words[0] . str_pad('', $spacing); foreach($words as $x => $word) { if($x == $word_count - 1 || $x == 0) continue; if($x < $word_count - 1) { $diff = $to_len - strlen($new_str) - (strlen(implode('', array_slice($words, $x)))); $new_str .= $word . str_pad('', floor($diff/($space_count - $x)), ' '); } } $new_str .= $words[$x]; return $new_str; } $tests = 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($tests as $word) { print $word . ' = ' . str_replace(' ', '_', justify($word, 48)) . '<br>'; }
我想念我在Python中的列表parsing…
<?php function justify ($str, $len) { // split by whitespace, remove empty strings $words = array_diff (preg_split ('/\s+/', $str), array ("")); // just space if no words if (count ($words) == 0) return str_repeat (" ", $len); // add empty strings if only one element if (count ($words) == 1) $words = array ("", $words[0], ""); // get number of words and spaces $wordcount = count ($words); $numspaces = $wordcount - 1; // get number of non-space characters $numchars = array_sum (array_map ("strlen", $words)); // get number of characters remaining for space $remaining = $len - $numchars; // return if too little spaces remaining if ($remaining <= $numspaces) return substr (implode (" ", $words), 0, $len); // get number of spaces per space $spaces_per_space = $remaining / $numspaces; $spaces_leftover = $remaining % $numspaces; // make array for spaces, spread out leftover spaces $spaces = array_fill (0, $numspaces, $spaces_per_space); while ($spaces_leftover--) $spaces[$numspaces - $spaces_leftover - 1]++; $spaces[] = 0; // make count ($words) == count ($spaces) // join it all together $result = array (); foreach ($words as $k => $v) array_push ($result, $v, str_repeat (" ", $spaces[$k])); return implode ($result); } ?>
这是我的尝试。
function justify($str_in, $desired_length) { foreach ($str_in as &$line) { $words = explode(' ', $line); $word_count = count($words) - 1; $spaces_to_fill = $desired_length - strlen($line) + $word_count; if (count($words) == 1) { $line = str_repeat('_', ceil($spaces_to_fill/2)) . $line . str_repeat('_', floor($spaces_to_fill/2)); continue; } $next_space = floor($spaces_to_fill/$word_count); $leftover_space = $spaces_to_fill % $word_count; $line = array_shift($words); foreach($words as $word) { $extra_space = ($leftover_space) ? ceil($leftover_space / $word_count) : 0; $leftover_space -= $extra_space; $line .= str_repeat('_', $next_space + $extra_space) . $word; } } return $str_in; }
我试图保持相对简洁，这影响了可读性。 但是，它是如何工作的：
对于每个条目，我们将这些单词分成一个数组$words 。 因为我们可能需要空格前后的空格，所以我们还在数组的开始和结尾添加了一个空string。
我们计算$leftover_space空间$leftover_space （也就是我们需要插入的空间），并将其除以单词的数量$word_count ，所以我们知道每个单词之间要放入多less个空格的平均值。
每当我们添加一个单词的时候，我们还会添加一些空格$extra_space ，具体取决于剩下的数量。 之后，我们删除$leftover_space添加的$leftover_space 。
示例输出
$data = justify($data, 48); print_r($data); Array ( [0] => 123456789012345678901234567890123456789012345678 [1] => hello_______world_______there_______ok______then [2] => ______________________hello_____________________ [3] => ok__________________________________________then [4] => this__string__is_almost_certainly_longer_than_48 [5] => two________________________________________words [6] => three__________________ok__________________words [7] => 1_____2_____3_____4_____5_____6_____7_____8____9 )
I think this is fully working: (the "_" is just keeping the space visible)
function justify($str_in, $desired_length) { $str_in = preg_replace("!\s+!"," ",$str_in); // get rid of multiple spaces $words = explode(" ",$str_in); // break words $num_words = sizeof($words); // num words if ($num_words==1) { return str_pad($str_in,$desired_length,"_",STR_PAD_BOTH); } else { $num_chars = 0; $lenwords = array(); for($x=0;$x<$num_words;$x++) { $num_chars += $lenwords[$x] = strlen($words[$x]); } $each_div = round(($desired_length - $num_chars) / ($num_words-1)); for($x=0,$sum=0;$x<$num_words;$x++) { $sum += ($lenwords[$x] + ($x<$num_words-1 ? $each_div : 0)); } $space_to_addcut = ($desired_length - $sum); for($x=0;$x<$num_words-1;$x++) { $words[$x] .= str_repeat("_",$each_div+($each_div>1? ($space_to_addcut<0?-1:($space_to_addcut>0?1:0)) :0)); if ($each_div>1) { $space_to_addcut += ($space_to_addcut<0 ? 1 : ($space_to_addcut>0?-1:0) ); } } return substr(implode($words),0,$desired_length); } }
编辑：
Function now get rid of multiple spaces between words as well. How it works ( in short ):
- removes continuous spaces between words
- count words so if one (the 'hello' example) just padding both and echo it.
- ..otherwise count the characters of the used words
- calculate the global and partial space to add (the '_' in example).
- calculate the extra space to add (string len < desired) OR remove (string len > desired) and apply it to padding.
- final, reduce the final string to desired length.
TESTING:
$tests = array( 'hello world there ok then', 'hello', 'ok then', 'this string is almost certainly longer than 48 I think', 'three ok words', '1 2 3 4 5 6 7 8 9', 'Lorem Ipsum is simply dummy text' ); $arr = array(); foreach($tests as $key=>$val) { $arr[$key] = justify($val,50); $arr[$key] .= " - (chars: ".strlen($arr[$key]).")"; } echo "<pre>".print_r($arr,TRUE)."</pre>";
AND THE RESULT:
Array ( [0] => hello________world_______there_______ok_______then - (chars: 50) [1] => ______________________hello_______________________ - (chars: 50) [2] => ok____________________________________________then - (chars: 50) [3] => this_string_is_almost_certainly_longer_than_48_I_t - (chars: 50) [4] => three___________________ok___________________words - (chars: 50) [5] => 1______2_____3_____4_____5_____6_____7_____8_____9 - (chars: 50) [6] => Lorem____Ipsum____is_____simply_____dummy_____text - (chars: 50) )
THAT WAS TOUGH 🙂
EDITED 2:
Function is now about 20% faster , because that benchmark touched me 🙂
The (Semi-Long) Solution
It's taken me a while to perfect (probably much, much longer than an interviewer would have allowed for), but I've come up with an elegant, 162 line OOP solution to this problem. I included functionality to allow for the justifying of a single string, array of strings (already separated into lines) or a long string that needs to be broken up into lines of a maximum width first. Demos follow the code block.
Important Note: This class will only work in PHP 5.4. I realized this when running a version on my own server PHP (5.3.6) to get profiling stats with XDebug. PHP 5.3 complains about my use of Added support for PHP 5.3! $this in the anonymous function. A quick check of the docs on anonymous functions reveals that $this could not be used in the context of an anonymous function until 5.4. If anyone can find a clean workaround to this, please drop it in the comments.
<?php class Justifier { private $text; public function __construct($text) { if(!is_string($text) && !is_array($text)) { throw new InvalidArgumentException('Expected a string or an array of strings, instead received type: ' . gettype($text)); } if(is_array($text)) { // String arrays must be converted to JustifierLine arrays $this->text = array_map(function($line) { return JustifierLine::fromText($line); }, $text); } else { // Single line of text input $this->text = $text; } } public function format($width = null) { // Strings have to be broken into an array and then jusitifed if(is_string($this->text)) { if($width == null) { throw new InvalidArgumentException('A width must be provided for separation when an un-split string is provided'); } if($width <= 0) { throw new InvalidArgumentException('Expected a positive, non-zero width, instead received width of ' . $width); } // Break up a JustifierLine of all text until each piece is smaller or equal to $width $lines = array(JustifierLine::fromText($this->text)); $count = 0; $newLine = $lines[0]->breakAtColumn($width); while($newLine !== null) { $lines[] = $newLine; $newLine = $lines[++$count]->breakAtColumn($width); } } else { $lines = $this->text; // Allow for fluid width (uses longest line with single space) if($width == NULL) { $width = -1; foreach($lines as $line) { // Width of line = Sum of the lengths of the words and the spaces (number of words - 1) $newWidth = $line->calculateWordsLength() + $line->countWords() - 1; if($newWidth > $width) { // Looking for the longest line $width = $newWidth; } } } } // Justify each element of array (PHP 5.4 ONLY) //$output = array_map(function($line) use ($width) { // return $this->justify($line, $width); //}, $lines); // Support for PHP 5.3 $output = array(); foreach($lines as $line) { $output = $this->justify($line, $width); } // If a single-line is passed in, a single line is returned if(count($output)) { return $output[0]; } return $output; } private function justify(JustifierLine $line, $width) { // Retrieve already calculated line information $words = $line->extractWords(); $spaces = $line->countWords() - 1; $wordLens = $line->findWordLengths(); $wordsLen = $line->calculateWordsLength(); $minWidth = $wordsLen + $spaces; $output = ''; if($minWidth > $width) { throw new LengthException('A minimum width of ' . $minWidth . ' was required, but a width of ' . $width . ' was given instead'); } // No spaces means only one word (center align) if($spaces == 0) { return str_pad($words[0], $width, ' ', STR_PAD_BOTH); } for(;$spaces > 0; $spaces--) { // Add next word to output and subtract its length from counters $output .= array_shift($words); $length = array_shift($wordLens); $wordsLen -= $length; $width -= $length; if($spaces == 1) { // Last Iteration return $output . str_repeat(' ', $width - $wordsLen) . $words[0]; } // Magic padding is really just simple math $padding = floor(($width - $wordsLen) / $spaces); $output .= str_repeat(' ', $padding); $width -= $padding; } } } class JustifierLine { private $words; private $numWords; private $wordLengths; private $wordsLength; public static function fromText($text) { // Split words into an array preg_match_all('/[^ ]+/', $text, $matches, PREG_PATTERN_ORDER); $words = $matches[0]; // Count words $numWords = count($words); // Find the length of each word $wordLengths = array_map('strlen', $words); //And Finally, calculate the total length of all words $wordsLength = array_reduce($wordLengths, function($result, $length) { return $result + $length; }, 0); return new JustifierLine($words, $numWords, $wordLengths, $wordsLength); } private function __construct($words, $numWords, $wordLengths, $wordsLength) { $this->words = $words; $this->numWords = $numWords; $this->wordLengths = $wordLengths; $this->wordsLength = $wordsLength; } public function extractWords() { return $this->words; } public function countWords() { return $this->numWords; } public function findWordLengths() { return $this->wordLengths; } public function calculateWordsLength() { return $this->wordsLength; } public function breakAtColumn($column) { // Avoid extraneous processing if we can determine no breaking can be done if($column >= ($this->wordsLength + $this->numWords - 1)) { return null; } $width = 0; $wordsLength = 0; for($i = 0; $i < $this->numWords; $i++) { // Add width of next word $width += $this->wordLengths[$i]; // If the line is overflowing past required $width if($width > $column) { // Remove overflow at end & create a new object with the overflow $words = array_splice($this->words, $i); $numWords = $this->numWords - $i; $this->numWords = $i; $wordLengths = array_splice($this->wordLengths, $i); $tempWordsLength = $wordsLength; $wordsLength = $this->wordsLength - $wordsLength; $this->wordsLength = $tempWordsLength; return new JustifierLine($words, $numWords, $wordLengths, $wordsLength); } $width++; // Assuming smallest spacing to fit // We also have to keep track of the total $wordsLength $wordsLength += $this->wordLengths[$i]; } return null; } }
演示
Original Question (Justifying Lines of Text to width = 48)
You can pass in an array of many strings or just one string to Justifier . Calling Justifier::format($desired_length) will 总是 return an array of justified lines * if an array of strings or string that required segmentation was passed to the constructor. Otherwise, a string will be returned. ( Codepad Demo )
$jus = new Justifier(array( 'hello world there ok then', 'hello', 'ok then', 'two words', 'three ok words', '1 2 3 4 5 6 7 8 9' )); print_r( $jus->format(48) );
产量
Array ( [0] => hello world there ok then [1] => hello [2] => ok then [3] => two words [4] => three ok words [5] => 1 2 3 4 5 6 7 8 9 )
You may notice I omitted one of the OP's test lines. This is because it was 54 characters and would exceed the $desired_length passed to Justifier::format() . The function will throw an IllegalArgumentException for widths that aren't positive, non-zero numbers that exceed or equal to the minimum width. The minimum width is calculated by finding the longest line (of all the lines passed to the constructor) with single spacing.
Fluid Width Justifying With An Array of Strings
If you omit the width, Justifier will use the width of the longest line (of those passed to the constructor) when single spaced. This is the same calculation as finding the minimum width in the previous demo. ( Codepad Demo )
$jus = new Justifier(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' )); print_r( $jus->format() );
产量
Array ( [0] => hello world there ok then [1] => hello [2] => ok then [3] => this string is almost certainly longer than 48 I think [4] => two words [5] => three ok words [6] => 1 2 3 4 5 6 7 8 9 )
Justifying a Single String of Text (width = 48)
I've also included a feature in the class which allows you to pass a single, non-broken string to the constructor. This string can be of any length. When you call Justifier::format($desired_length) the string is broken into lines such that each line is filled with as much text as possible and justified before starting a new line. The class will complain with an InvalidArgumentException because you must provide a width into which it can break the string. If anyone can think of a sensible default or way to programmatically determine a default for a string, I'm completely open to suggestions. ( Codepad Demo )
$jus = new Justifier( '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' ); print_r( $jus->format(48) );
产量
Array ( [0] => hello world there ok then hello ok then this [1] => string is almost certainly longer than 48 I [2] => think two words three ok words 1 2 3 4 5 6 7 8 9 )
这是我的解决scheme。 For what it's worth, it took me about 20 minutes to make both the justify function and acceptance tests for it; 5 of those minutes debugging the justify function. Also, I used notpad++ instead of a more robust IDE to try to simulate to some extent the interview environment.
I think this might be too large of a problem for a whiteboard interview question, unless the interviewer lets you write in pseudocode and is more interested in your thought process that what you are putting on the board.
<?php function justify($str_in, $desired_length) { $words = preg_split("/ +/",$str_in); // handle special cases if(count($words)==0) { return str_repeat(" ",$desired_length); } // turn single word case into a normal case if(count($words)==1) { $words = array("",$words[0],""); } $numwords = count($words); $wordlength = strlen(join("",$words)); // handles cases where words are longer than the desired_length if($wordlength>($desired_length-$numwords)) { return substr(join(" ",$words),0,$desired_length); } $minspace = floor(($desired_length-$wordlength)/($numwords-1)); $extraspace = $desired_length - $wordlength - ($minspace * ($numwords-1)); $result = $words[0]; for($i=1;$i<$numwords;$i++) { if($extraspace>0) { $result.=" "; $extraspace--; } $result.=str_repeat(" ",$minspace); $result.=$words[$i]; } return $result; } function acceptance_justify($orig_str, $just_str, $expected_length) { // should be the correct length if(strlen($just_str)!=$expected_length) { return false; } // should contain most of the words in the original string, in the right order if(preg_replace("/ +/","",substr($orig_str,0,$expected_length)) != preg_replace("/ +/","",substr($just_str,0,$expected_length))) { return false; } //spacing should be uniform (+/- 1 space) if(!preg_match("/( +)/",$just_str,$spaces)) { return false; } $space_length=strlen($spaces[0]); $smin=$space_length; $smax=$space_length; for($i=1;$i<count(@spaces);$i++) { $smin=min($smin,strlen($spaces)); $smax=max($smax,strlen($spaces)); } if(($smax-$smin)>1) { return false; } return true; } function run_test($str,$len) { print "<pre>"; print "$str ==> \n"; $result = justify($str,$len); print preg_replace("/ /",".",$result) . "\n"; print acceptance_justify($str,$result,$len)?"passed":"FAILED"; print "\n\n</pre>"; } run_test("hello world there ok then",48); run_test("hello",48); run_test("this string is almost certainly longer than 48 I think",48); run_test("two words",48); run_test("three ok words",48); run_test("1 2 3 4 5 6 7 8 9",48);
Here's a little bit different implementation just towards the end.
<?php function justify($str, $to_len) { $str = trim($str); $strlen = strlen($str); if($str == '') return ''; if($strlen >= $to_len) { return substr($str, 0, $to_len); } $words = explode(' ', $str); $word_count = count($words); $space_count = $word_count - 1; if($word_count == 1) { return str_pad($str, $to_len, ' ', STR_PAD_BOTH); } $space = $to_len - $strlen + $space_count; $per_space = floor($space/$space_count); $spaces = str_pad('', $per_space, ' '); $curr_word = implode($words, $spaces); while(strlen($curr_word) < $to_len){ $curr_word = substr($curr_word,0,preg_match("[! ][".$spaces."][! ]",$curr_word))." ".preg_match("[! ][".$spaces."][! ]",$curr_word)); } return $curr_word; ?>
I'm not sure about the regexp , I just meant $spaces and not next space.
