問題描述
下面是有關(guān)這個問題的描述部分。
We are building a word processor and we would like to implement a “word-wrap” functionality.
Given a list of words followed by a maximum number of characters in a line, return a collection of strings where each string element represents a line that contains as many words as possible, with the words in each line being concatenated with a single ‘-’ (representing a space, but easier to see for testing). The length of each string must not exceed the maximum character length per line.
Your function should take in the maximum characters per line and return a data structure representing all lines in the indicated max length.
我們希望構(gòu)建一個字符串處理函數(shù)，這個字符串處理函數(shù)將會對給定輸入的字符串和參數(shù)進(jìn)行處理。
我們首先將會定義一個字符串的數(shù)組，在這個字符串的數(shù)組中每一個元素都是存儲為一個單詞，同時我們將會給出一個整數(shù)類型的參數(shù)。你的方法將會對上面輸入的 2 個參數(shù)進(jìn)行運算，在每一個單詞和每一個單詞之間會添加一個字符 ”-“ 來進(jìn)行區(qū)分，同時新生成的數(shù)組或者 List 每一元素的字符串長度將不能超過給出的字符串的長度。
如果你新生成的元素是以橫杠結(jié)尾的話，那么你需要刪除這個橫杠。
下面給出了這個問題的示例，以便于你參考。
輸入?yún)?shù) 1輸入?yún)?shù) 2輸出
words1 = [ “The”, “day”, “began”, “as”, “still”, “as”, “the”, “night”, “abruptly”, “l(fā)ighted”, “with”, “brilliant”, “flame” ]13[ “The-day-began”, “as-still-as”, “the-night”, “abruptly”, “l(fā)ighted-with”, “brilliant”, “flame” ]
words1 = [ “The”, “day”, “began”, “as”, “still”, “as”, “the”, “night”, “abruptly”, “l(fā)ighted”, “with”, “brilliant”, “flame” ]20[ “The-day-began-as”, “still-as-the-night”, “abruptly-lighted”, “with-brilliant-flame” ]
words2 = [ “Hello” ]5[ “Hello” ]
words3 = [ “Hello”, “world” ]5[ “Hello”, “world” ]
words4 = [“Well”, “Hello”, “world” ]5[ “Well”, “Hello”, “world” ]
words5 = [“Hello”, “HelloWorld”, “Hello”, “Hello”]20[ “Hello-HelloWorld”, “Hello-Hello” ]
上面給出的是是測試用的示例，其中輸入?yún)?shù) words1 到 5 就是定義的變量名而已，不需要過度關(guān)注。
這個題目的難度還是比較大的，尤其是在沒有開發(fā)工具進(jìn)行編譯的時情況下。
這個題目是indeed.com的一個在線面試測試題。這個公司的在線面試測試使用的是第三方公司提供的評估工具，主持面試的人可能是對技術(shù)并不是非常了解的人，或者是對技術(shù)比較了解的人，我們不清楚具體的情況。
但是在面試過程中，他們只注重程序的輸出和面試的結(jié)果，至于你的思路或者你的想法，主持面試的人可能并不十分關(guān)注，同時也不怎么會聽你的解釋，很多時候你都會是在自言自語。
整體感覺面試互動很少，更多的時候是你在對著屏幕說話。
最開始的時候，我的思路是首先對給出的數(shù)組進(jìn)行遍歷，當(dāng)取得第一個元素的時候，將元素后面添加橫杠，然后與長度進(jìn)行對比，如果長度超過了給定的長度的話那么就刪除橫杠后壓入需要返回的列表中。
如果長度少于返回的長度，那么再取出下一個元素，同時再結(jié)尾再添加橫桿后進(jìn)行判斷，然后再確定橫杠的處理。
這個題目的主要問題就在于橫杠的處理，有時候橫杠在結(jié)尾，有時候橫杠在開頭，你需要一個一個判讀。
在隨后的測試中，我發(fā)現(xiàn)一直是橫杠處理不好，結(jié)果導(dǎo)致沒有完全通過最后的測試，就是上面測試用例的第二行。
因為這個題目時間有限，并且我們還不能使用 StringUtils 來進(jìn)行一些快速的字符串處理，因此我沒有在規(guī)定的時間內(nèi)完成所有的測試。在隨后結(jié)束面試后，我再仔細(xì)思考了下問題后發(fā)現(xiàn)其實我們還可以有其他的辦法來進(jìn)行操作。
我使用下面的思路，并且完成了代碼的修改。
首先我們需要將輸入的數(shù)組變成一個長的字符串，單詞之間使用橫杠分隔。例如，[ “Hello”, “world” ] 將會變成字符串為：Hello-world。
在完成上面的操作后，我們需要使用一個 while 循環(huán)來做。
首先在 while 循環(huán)中判讀整個字符串長度小于給定的長度，這個時候需要直接返回，然后中斷循環(huán)。
下一步，對字符串，從頭到給定的長度進(jìn)行截斷后獲得子字符串，隨后對子字符串進(jìn)行判斷，如果這個子字符串是以橫杠結(jié)尾的話，刪除橫杠然后壓入需要返回的數(shù)組，然后更新需要處理的字符串為截斷后余下的字符串。
如果按照給定的長度進(jìn)行截斷后，你獲得最后的一個字符不是橫杠，那么我們就知道你截斷到了單詞上，獲得的子字符串中，找到最后一個橫杠，然后獲得索引的 ID，在獲得這個索引的 ID 后對需要處理的字符串按照索引 ID 進(jìn)行截斷。
然后刪除掉最后的橫杠壓入需要返回的列表中。
在余下的字符串中可能遇到的情況是目前你將會是橫杠開頭的，因此你還需要刪除掉余下字符串中開頭和結(jié)尾的橫杠。
繼續(xù)上面的處理，直到需要處理的字符串長度小于給定的長度后中斷循環(huán)。
上圖是對上面思路 2 中的算法進(jìn)行測試后的返回結(jié)果，從結(jié)果中可以看到滿足需要輸出的預(yù)期。
