Last Updated on 2022-03-24 by Clay
題目
The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.
The numeric value of a string consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.
You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.
Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.
Example 1:
Input: n = 3, k = 27 Output: "aay" Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
Example 2:
Input: n = 5, k = 73 Output: "aaszz"
Constraints:
1 <= n <= 105n <= k <= 26 * n
題目僅會輸入兩個數字 n 以及 k，其中 n 代表最終回傳的字串長度，k 代表字串中的字母數值加總的總值（a=1 ... z=26），而我們要回傳的字串乍看之下有很多種可能，但僅需回傳字典序最小的字串即可。
比方說 aab 和 aba 總值皆為 4，但應該回傳字典序比較小的 aab。
解題思路
Greedy 解法
由於是要返回最小的字典序字串，故其實可以使用貪婪解的方法去求出答案。
（註：所謂的字典序就是 aab 和 aba 雖然都是同樣的字元組成，但前者比後者小）
比方說，一開始假設字串中所有的的字母都是 a，這樣我們當前值剛好為返回字串的長度、亦即為 n，接著我們再去計算與目標值 k 之間的差距；按照貪婪解法，我們嘗試從最後一個字元開始置換成 z，並將當前值加上 25（原本的 a 為 1 而 z 為 26，是故增加 25）...... 如果當前值跟 k 之間的差距不足 25，則剛好填入相差數字所代表的字母。
以 Example 2 來做範例，n = 5, k = 73：
s="aaaaa", val=5 s="aaaaz", val=30 s="aaazz", val=55 （注意，這邊跟所求的 k 值僅相差 18，填入對應的數字 19 即可 –– 因為需要替換掉一個 a） s="aaszz", val=73 <= 答案！
Greedy 解法複雜度
| Time complexity | O(n) |
| Space complexity | O(n) |
Greedy 解法 C++ 範例程式碼
class Solution {
public:
string getSmallestString(int n, int k) {
// Init
string s(n, 'a');
int i = s.size() - 1;
// Distance
k -= n;
// Matching the target string
while (k != 0) {
if (k > 25) {
s[i] = 'z';
k -= 25;
}
else {
s[i] = k + 'a';
k = 0;
}
--i;
}
return s;
}
};Greedy 解法 Python 範例程式碼
class Solution {
public:
string getSmallestString(int n, int k) {
// Init
string s(n, 'a');
int i = s.size() - 1;
// Distance
k -= n;
// Matching the target string
while (k != 0) {
if (k > 25) {
s[i] = 'z';
k -= 25;
}
else {
s[i] = k + 'a';
k = 0;
}
--i;
}
return s;
}
};