Prepare a notification of the given message which will be displayed on a mobile device. The message is made of words separated by single spaces. The length of the notification is limited to K characters. If the message is too long to be displayed fully, some words from the end of the message should be cropped, keeping in mind that: the notification should be as long as possible; only whole words can be cropped; if any words are cropped, the notification should end with '...'; the dots should be separated from the last word by a single space; the notification may not exceed the K-character limit, including the dots. If all the words need to be cropped, the notification is '...' (three dots without a space). Write up the func in the editor Given a string message and an integer K, returns the notification to display, which has no more than K chars, as described above.

Constraints

• K is an integer within the range [3, 500]
• the len of string msg i within the range [1, 500]
• string msg is made of English letters ('a' - 'z', 'A-Z') and space ('')
• msg does not contains spaces at the beginning of at the end
• words are separated by a single space (there are never 2 or more consecutive sapces)

Example 1

Input:

message = "And now here is my secret"
K = 15

Output:

"And now ..."

Explanation: no explanation is provided

Example 2

Input:

message = "There is an animal with four legs"
K = 15

Output:

"There is an ..."

Explanation: no explanation is provided

Example 3

Input:

message = "super dog"
K = 4

Output:

"..."

Explanation: no explanation is provided

Example 4

Input:

message = "how are you"
K = 20

Output:

"how are you"

Explanation: no explanation is provided

解法

若整条消息长度 ≤ K 直接返回。否则贪心从前往后累计单词，要求累计 + " ..." 不超过 K；选最长合法前缀。若一个词也放不下则返回 "..."。复杂度 O(|message|)。

def prepare_notification(message: str, K: int) -> str:
    if len(message) <= K:
        return message
    words = message.split()
    chosen = []
    cur = 0
    for w in words:
        extra = len(w) if not chosen else len(w) + 1
        if cur + extra + 4 <= K:
            chosen.append(w)
            cur += extra
        else:
            break
    if not chosen:
        return "..."
    return " ".join(chosen) + " ..."

class Solution {
    String prepareNotification(String message, int K) {
        if (message.length() <= K) return message;
        String[] words = message.split(" ");
        StringBuilder sb = new StringBuilder();
        int cur = 0;
        for (String w : words) {
            int extra = sb.length() == 0 ? w.length() : w.length() + 1;
            if (cur + extra + 4 <= K) {
                if (sb.length() > 0) sb.append(' ');
                sb.append(w);
                cur += extra;
            } else break;
        }
        if (sb.length() == 0) return "...";
        sb.append(" ...");
        return sb.toString();
    }
}

class Solution {
public:
    string prepareNotification(string message, int K) {
        if ((int) message.size() <= K) return message;
        vector<string> words;
        string w;
        for (char c : message) {
            if (c == ' ') { if (!w.empty()) { words.push_back(w); w.clear(); } }
            else w += c;
        }
        if (!w.empty()) words.push_back(w);
        string out;
        int cur = 0;
        for (auto& wd : words) {
            int extra = out.empty() ? (int) wd.size() : (int) wd.size() + 1;
            if (cur + extra + 4 <= K) {
                if (!out.empty()) out += ' ';
                out += wd;
                cur += extra;
            } else break;
        }
        if (out.empty()) return "...";
        return out + " ...";
    }
};

To solve this problem, you gonna need to write up the func in the editor What you've been given: int Z What your func is gonna do:

1. find the smallest num that is > than Z.
2. total of all the digits of the num you find must == 2 * (total of all digits of Z) Memo : When solving this problem, you can mainly focus on correctness. As for your code performance, it would not be the focus this time .

Constraints

• 1 ≤ Z ≤ 500.

Example 1

Input:

N = 10

Output:

11

Explanation: As we can see, 11 is the smallest num that is > 10. What is the total sum of all digits of 10? The ans is 1 + 0 = 1... What is the total sum of all digits of 11? The ans is 1 + 1 = 2... 2 == 1 * 2, so 11 should be returned.

Example 2

Input:

N = 14

Output:

19

Explanation: The total of all the digits of 19 (1 + 9 = 10) == 2 * total of digits of 14 (1 + 4 = 5)

Example 3

Input:

N = 99

Output:

9999

Explanation: The sum of digits of 9999 (9 + 9 + 9 + 9 = 36) == total of digits of 99 (9 + 9 = 18).