string - 将 SMS 分成 30 个字符大小的 SMS

Question

问题陈述如下——

There is a text messaging service.It provides with an API to send SMSes to a user, 
but they can be at most 30 characters long. 
Also it doesn't guarantee the order in which the messages will be received.


You have to build a function which splits the text in chunks so that it can 
be sent in multiple messages. Each chunk has to be :
- upto 30 characters long
- no word should be split in the middle
- each chunk has to have its order suffixed in the form of '(k/n)' 
  e.g. "this is the first chunk (1/2)", "this is the second chunk (2/2)"
- if the text provided to the function is within 30 characters limit, 
  no ordering should be suffixed

Input/Output Format 
Each test case consists of a single line of words. Words are space 
separated. Any other character other than space is considered part of 
the word. For each test case, output the minimum number of chunks C 
required to fit the entire SMS. 

Restrictions
1 <=C<= 99; Input will be such that C remain in this mentioned limit 
if your algorithm is optimal. No word will have a length that does 
not fit in a single chunk (even after considering the suffix).

Sample Input: 
The best lies are always mixed with a little truth 
There is no creature on earth half so terrifying as a truly just man!!!!!
You know nothing, Jon Snow 

Sample Output 
3
3
1

Explanation: 
In first case, we will have to split as below 

The best lies are always (1/3)
mixed with a little (2/3)
truth (3/3)

First line is fully utilised with 30 characters in it. 
Second line has 25 characters but if we try to fit last word in this line, 
it becomes 31 characters. 'mixed with a little truth (2/2) 
Hence we must split into 3 parts as above.

我的方法 -> 主要是先找到大致的 block 数，然后再对其进行扩展，但这没有用。我想知道是否有可能首先从数学上计算出需要多少 block ，或者我们实际上是否必须构建 block 并查看，然后我们如何在不知道“k/n”的“n”的情况下构建 block ？

Answer 1

您必须知道 n 才能知道每个 block 中可以放入多少个单词，因为这取决于 n。

即使 n 以 99 进制表示，只需要一个字符，您仍然需要单独检查每个单词的长度。

我怀疑词 block 之间的最佳分布不是将词(和空格)放入行中直到下一个项目不适合的简单方法:它可能会更好尽早在某个地方制作一些较小的 block ，以便以后更好地打包。但是，这不是 cutting stock problem因为必须保留顺序。

通过简单的方法，我的意思是假设少于10个 block 来打包单词，如果没有则根据少于100个 block 重新开始，例如在VB.NET中:

Imports System.Text
Imports System.Text.RegularExpressions

Module Module1

    Function NumberLength(n As Integer) As Integer
        Return If(n < 10, 1, 2)
    End Function

    Sub Main()
        Dim msg = "Escobazos tu dios pisan amor sus el las grupos se y no de los pulso mudas muerte mi inocentes vilo los las bajaba viciosa tierra de amor horizonte la se deja de tierra heridas ni los la es los recodos horizonte diminutas la de es nube talco hombrecillo de piel los se escobazos nadadora de bajo consume las se con ni las en por que donde tierra es sillas el de de que latido viva lo a grupos torre escaleras desnudo dolor me a la la quedo que sepultura signos criaturas de desnudo subía la húmedo desnuda latido nube quedo de la el nadadora el cielo dolor arroyo escobazos quedo donde de amor venas el viva poniendo desangradas torre que resonancia los fría ansioso el de subía el tierra todo se ansioso manteles por amor amor con de el quemadas resonancia con mujer el y que luna los bajaba quedo los yo a alegrísima de ilesa huido el mi que los se bajo la hombrecillo luna en de vilo es de el aire despenada que latido aire para sus horizonte todo muelles heridas viva hule tierra para huido de las a los llenando los que por húmedo tránsito tierra la la aire olvidando recodos de de la ligeros los término por luna bajaba tierra llenando del al que bajo de que de a pupila mueven que grupos se tránsito los ciudades de de nino mármol vuelve lenguas se los pisotean la vengo con faraón tránsito ballenas la se los tierra del escaleras de tierra nunca lenta se musgos que desgarrados la de desgarrados la imperturbable la resonancia y duro subía tierra me mi de talco escaleras el duro los desangradas sus buscando desangradas de pies algodón golondrina por que las no larga con diana que el en imperturbable de los luna al la huevos muertos las los las larga para borrachos de el aire los la bajo tierra fría talco los los comida en llanura en en los todo que en olvidando es de el de tu la de los muerte los las de que húmedo llenando de los pasan los hombrecillo se duro lenta ballenas ninos hule la con a la tierra por gustada es y se tierra amor las recientes manteles tierra de para signos el es un diana es del dios es imperturbable de consume de muelles luna para al nube tierra bajo apariencia encuentro es diminutas"
        Dim nPart = 1
        Dim nPartsTotal = 1 'assume 9 or less parts
        Dim nPartsTotalLength = 1
        Dim maxPartLength = 30

        If msg.Length <= maxPartLength Then
            Console.WriteLine("1")
            Console.ReadLine()
            Exit Sub
        End If

        Dim words = Regex.Split(msg, "( )")

        Dim suffixLength = 5 ' up to 9 parts

        Dim pos = 0
        Dim nWord = 0

        Dim thisPart As New StringBuilder
        Dim partText As New List(Of String)

        While nWord < words.Count()
            suffixLength = 3 + NumberLength(nPart) + nPartsTotalLength
            If pos + suffixLength + words(nWord).Length <= maxPartLength Then
                pos += words(nWord).Length
                nWord += 1
                thisPart.Append(words(nWord - 1))
            Else
                partText.Add(thisPart.ToString())
                pos = 0
                nPart += 1
                nPartsTotal += 1
                thisPart.Clear()

                If nPartsTotal > 9 AndAlso nPartsTotalLength = 1 Then
                    ' start again knowing that there are more than 9 parts required
                    nPartsTotalLength = 2
                    nPart = 1
                    nPartsTotal = 1
                    nWord = 0
                    partText.Clear()
                End If
            End If

        End While

        If thisPart.Length > 0 Then
            partText.Add(thisPart.ToString())
        End If

        Console.WriteLine(nPartsTotal)
        Console.WriteLine(New String("|"c, maxPartLength)) ' show max length

        For i = 1 To partText.Count()
            Console.WriteLine($"{partText(i - 1)}({i}/{nPartsTotal})")
        Next

        Console.ReadLine()

    End Sub

End Module

这恰好生成了 99 个 block 。该问题不要求实际 block 的输出 - 示例代码的那部分可以查看，以防明显不同的算法可以做得更好。