前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode: 68. Text Justification [✗]

leetcode: 68. Text Justification [✗]

作者头像
JNingWei
发布2018-09-27 16:59:05
4130
发布2018-09-27 16:59:05
举报
文章被收录于专栏:JNing的专栏

Problem

代码语言:javascript
复制
# Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
#
# You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
#
# Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
#
# For the last line of text, it should be left justified and no extra space is inserted between words.
#
# For example,
# words: ["This", "is", "an", "example", "of", "text", "justification."]
# L: 16.
#
# Return the formatted lines as:
# [
#     "This    is    an",
#     "example  of text",
#     "justification.  "
# ]
# Note: Each word is guaranteed not to exceed L in length.

AC

代码语言:javascript
复制
class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        lines = []
        i = 0
        while i<len(words):
            llen = 0  
            cur = i
            while i<len(words):
                llen += len(words[i])
                if llen>maxWidth:
                    llen -= len(words[i])
                    break
                llen+=1
                i+=1

            llen -=1
            if i != len(words):
                wordcnt = i-cur
                extra = maxWidth-llen                 
                if wordcnt>1:
                    spaces = extra/(wordcnt-1)
                    r = extra%(wordcnt-1)
                else:
                    spaces = extra
                    r = 0
            else:
                spaces = 0
                r = 0

            line = ""
            for word in words[cur:i]:
                line += word
                line += " "*(spaces+1)
                if r>0:
                    line += " "
                    r -= 1

            line = line[:maxWidth]
            if len(line)<maxWidth:
                line+=" "*(maxWidth-len(line))

            lines.append(line)

        return lines


# Time:  O(n)
# Space: O(k), k is maxWidth.
class Solution2(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        def addSpaces(i, spaceCnt, maxWidth, is_last):
            if i < spaceCnt:
                return 1 if is_last else (maxWidth // spaceCnt) + int(i < maxWidth % spaceCnt)
            return 0

        def connect(words, maxWidth, begin, end, length, is_last):
            s = []  # The extra space O(k) is spent here.
            n = end - begin
            for i in range(n):
                s += words[begin + i],
                s += ' ' * addSpaces(i, n - 1, maxWidth - length, is_last),
            # For only one word in a line.
            line = "".join(s)
            if len(line) < maxWidth:
                line += ' ' * (maxWidth - len(line))
            return line

        res = []
        begin, length = 0, 0
        for i in range(len(words)):
            if length + len(words[i]) + (i - begin) > maxWidth:
                res += connect(words, maxWidth, begin, i, length, False),
                begin, length = i, 0
            length += len(words[i])

        # Last line.
        res += connect(words, maxWidth, begin, len(words), length, True),
        return res


if __name__ == "__main__":
    assert Solution().fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16) \
           == ['This    is    an', 'example  of text', 'justification.  ']
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年11月19日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem
  • AC
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档