No Assumption to build the strings in the Array's Order


  • 0
    L

    I read through many times of the problem's description and didn't see anything forcing
    the solution to build strings in the order of the array, while the "greedy" wording makes
    me think I should NOT be limited to do it in the order of the array.

    You should pack your words in a greedy approach; that is,
    pack as many words as you can in each line
    

    Without such array-order assumption I wrote a much more complex solution to achieve but realized it with tears after a few fault test cases.

    This should be clarified during your interview, I believe, FYI.


  • 0
    L
    //This is the accepted solution by assuming array's order.
    public IList<string> FullJustify(string[] words, int maxWidth) {
        IList<string> result = new List<string>();
        IList<string> curLst = new List<string>();
        for (int i = 0, nextIndex = 0, curLen = 0; i < words.Length || curLst.Count != 0; i++){
            if (i == words.Length && curLst.Count != 0 || nextIndex + words[i].Length > maxWidth){
                int spaceAmount = maxWidth - curLen, slotAmount = curLst.Count - 1;
                StringBuilder sb = new StringBuilder();
                if (slotAmount == 0) sb.Append(curLst[0] + new string(' ', spaceAmount));
                else{
                    int mod = spaceAmount % slotAmount, cellSpace = spaceAmount / slotAmount;
                    foreach (var wd in curLst)
                        if (i != words.Length){
                            sb.Append(wd + new string(' ', cellSpace));
                            if (mod > 0){
                                sb.Append(' ');
                                mod--;
                            }
                        }
                        else sb.Append(wd + " ");
                    if (i == words.Length) sb.Append(new string(' ', spaceAmount - curLst.Count));
                }
                result.Add(sb.ToString().Substring(0, maxWidth));
                curLst.Clear();
                curLen = 0;
                nextIndex = 0;
                if (i == words.Length) break;
            }
            curLst.Add(words[i]);
            nextIndex += words[i].Length + 1;
            curLen += words[i].Length;
        }
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.