3838. Weighted Word Mapping

題目 / Problem

中文

給你一個字串陣列 words，每個字串是由小寫英文字母組成的單字。

另外給你一個長度為 26 的整數陣列 weights，其中 weights[i] 代表第 i 個小寫字母的權重（weights[0] 是 'a' 的權重，weights[1] 是 'b' 的權重，依此類推）。

一個單字的「權重」定義為它所有字元權重的總和。

對每個單字，先把它的權重對 26 取餘數（modulo 26），再用反向字母順序把這個餘數對應到一個小寫字母：0 -> 'z'、1 -> 'y'、…、25 -> 'a'。

把所有單字依序對應到的字元串接起來，回傳這個字串。

English

You are given an array of strings words, each made of lowercase English letters.

You are also given an integer array weights of length 26, where weights[i] is the weight of the i-th lowercase letter (weights[0] for 'a', weights[1] for 'b', and so on).

The weight of a word is the sum of the weights of its characters.

For each word, take its weight modulo 26, then map that result to a lowercase letter using reverse alphabetical order: 0 -> 'z', 1 -> 'y', …, 25 -> 'a'.

Concatenate the mapped characters for all words in order and return the resulting string.

Constraints / 限制 - 1 <= words.length <= 100 - 1 <= words[i].length <= 10 - weights.length == 26 - 1 <= weights[i] <= 100 - words[i] 只含小寫英文字母 / consists of lowercase letters.

Worked example / 範例

words = ["abcd","def","xyz"], weights = [5,3,12,14,1,...] - "abcd" → 5+3+12+14 = 34，34 % 26 = 8 → 'r' - "def" → 14+1+2 = 17，17 % 26 = 17 → 'i' - "xyz" → 7+7+2 = 16，16 % 26 = 16 → 'j'

Output: "rij"

名詞解釋 / Glossary

• 權重總和 / weight sum：把單字裡每個字元對應的權重加起來得到的數字。例如 "ab" 的權重 = weights['a'] + weights['b']。It is just an accumulated total.
• 取餘數 / modulo (%)：% 運算子回傳除法的餘數。例如 34 % 26 = 8，因為 34 = 26 × 1 + 8。Here it folds any large sum into the range 0..25.
• 字元算術 / character arithmetic：在 C/C++ 中字元其實是小整數（ASCII 碼）。c - 'a' 會把 'a' 變成 0、'b' 變成 1…，剛好就是這個字母在 weights 裡的索引（index）。'z' - value 則反過來，把一個數字轉回字母。
• 索引 / index：陣列中某個元素的位置編號，從 0 開始。weights[c - 'a'] 就是用字母換算出來的索引去查它的權重。
• 指標 / pointer (C)：在 C 裡 char * 是一個指向字元的位址。字串就是一串字元，以 '\0'（結尾標記）收尾。words[i] 是第 i 個字串。
• 動態配置記憶體 / dynamic allocation (malloc)：C 不能回傳「自動長大」的字串，所以我們用 malloc 向系統要一塊指定大小的記憶體來存答案，呼叫者用完後負責 free。

思路

最直接的想法就是照題目敘述一步一步模擬，因為資料量很小（最多 100 個單字，每個最多 10 個字母），完全不需要任何優化技巧。對每一個單字，我們從 0 開始累加，把單字裡每個字元 c 用 weights[c - 'a'] 查到權重後加進總和。c - 'a' 之所以正確，是因為字元在記憶體裡就是連續的整數編碼，'a' 減掉自己是 0、'b' 減 'a' 是 1，剛好對上 weights 的索引。累加完後對 26 取餘數，把總和「摺疊」進 0..25 的範圍。最後關鍵是反向對應：題目要 0 -> 'z'、25 -> 'a'，注意到 'z' 的編碼比 'a' 大 25，所以 'z' - value 正好能把 0 變 'z'、把 25 變 'a'。把每個單字算出來的字元依序寫進答案字串即可。因為每個字元只被看過一次，這已經是最佳解。

The simplest idea is to simulate the description directly, and since the input is tiny (at most 100 words of at most 10 letters), no clever optimization is needed at all. For each word, start a running sum at 0 and, for every character c, add weights[c - 'a']. The expression c - 'a' works because characters are just small integer codes laid out consecutively: 'a' - 'a' is 0, 'b' - 'a' is 1, and so on — exactly the indices into weights. After summing, take the result modulo 26 to fold it into the range 0..25. The crucial final step is the reverse mapping: the problem wants 0 -> 'z' and 25 -> 'a', and since 'z' sits 25 codes above 'a', the expression 'z' - value turns 0 into 'z' and 25 into 'a' automatically. Write each word's mapped character into the answer in order. Each character is touched exactly once, so this is already optimal.

逐步走查 / Walkthrough

Input: words = ["abcd","def","xyz"], weights[0..] = a=5, b=3, c=12, d=14, e=1, f=2, ..., x=7, y=7, z=2

• 結果字串逐步成長 / result grows: "r" → "ri" → "rij"
• 最後補上字串結尾標記 '\0' / append the terminating '\0'.
• Final output: "rij" ✅

Solution — C

// 演算法 / Algorithm:
// 對每個單字累加字元權重，sum % 26 得到 0..25，再用 'z'-value 反向對應成字母。
// For each word, sum its letter weights, take % 26, then map via 'z'-value (reverse order).
// 結果字串長度 = 單字數量，需動態配置記憶體回傳 / result length = number of words; malloc it.

char* mapWords(char** words, int wordsSize, int* weights, int weightsSize) {
    // 配置 wordsSize+1 個位元組：每個單字一個字元，加上結尾的 ''
    // Allocate wordsSize+1 bytes: one char per word, plus the terminating ''.
    char* result = (char*)malloc((wordsSize + 1) * sizeof(char));

    // 外層迴圈：處理第 i 個單字 / outer loop: handle the i-th word
    for (int i = 0; i < wordsSize; i++) {
        int sum = 0;                       // 這個單字的權重總和歸零 / reset this word's weight sum

        // 內層迴圈：走過單字的每個字元，直到遇到字串結尾 ''
        // Inner loop: walk each char of the word until the '' terminator.
        for (int j = 0; words[i][j] != ''; j++) {
            char c = words[i][j];          // 取出當前字元 / current character
            // c - 'a' 把字母轉成 0..25 的索引，再去 weights 查權重並累加
            // c - 'a' turns the letter into an index 0..25; look up its weight and add it.
            sum += weights[c - 'a'];
        }

        int value = sum % 26;              // 摺疊進 0..25 範圍 / fold into range 0..25
        // 'z' - value：value=0 -> 'z'，value=25 -> 'a'，正好是反向字母順序
        // 'z' - value: value 0 -> 'z', value 25 -> 'a' — exactly reverse alphabetical order.
        result[i] = (char)('z' - value);
    }

    result[wordsSize] = '';              // C 字串必須以 '' 結尾 / C strings must end with ''
    return result;                         // 回傳；呼叫端負責 free / caller is responsible for free
}

Solution — C++

// 演算法 / Algorithm:
// 對每個單字累加字元權重，% 26 得 0..25，再用 'z'-value 反向對應成字母並串接。
// For each word, sum its letter weights, take % 26, map via 'z'-value, and append.
class Solution {
public:
    string mapWords(vector<string>& words, vector<int>& weights) {
        string result;                     // 用 string 自動管理長度，免去手動配置記憶體
                                           // string auto-manages length; no manual malloc needed.
        result.reserve(words.size());      // 預留空間避免多次重新配置 / reserve to avoid reallocations

        // range-for：依序取出每個單字的參考 w，避免複製
        // range-based for loop: bind each word to reference w (no copy).
        for (const string& w : words) {
            int sum = 0;                   // 這個單字的權重總和 / this word's weight sum

            // 再用 range-for 走過單字裡的每個字元 c / iterate each char c of the word
            for (char c : w) {
                // c - 'a' 轉成 0..25 索引去查權重 / index 0..25 into weights via c - 'a'
                sum += weights[c - 'a'];
            }

            int value = sum % 26;          // 折進 0..25 / fold into 0..25
            // 反向對應：value=0 -> 'z'，value=25 -> 'a'；push_back 把字元接到字串尾端
            // Reverse map: 0 -> 'z', 25 -> 'a'; push_back appends the char to the string.
            result.push_back(static_cast<char>('z' - value));
        }

        return result;                     // string 會自動處理結尾，直接回傳即可 / return directly
    }
};

複雜度 / Complexity

• Time: O(N · L) — N 是單字數量，L 是單字平均長度。我們必須讀過每個單字的每個字元各一次來累加權重，這就是主要工作量。N is the number of words and L their average length; we read every character of every word exactly once to accumulate weights. With the given limits (≤100 words × ≤10 chars) this is at most ~1000 operations.
• Space: O(N) — 回傳的結果字串長度等於單字數量（再加一個結尾字元）。除此之外只用了幾個整數變數，是常數空間。The output string has one character per word (plus a terminator); aside from a few integer variables, no extra space is used.

Pitfalls & Edge Cases

• 反向對應方向搞反 / Reversed mapping direction：很容易誤寫成 'a' + value（正向），但題目要 0 -> 'z'，必須是 'z' - value。記住 0 對應 'z'、25 對應 'a'。It's tempting to write 'a' + value; the problem requires 'z' - value.
• 忘記 '\0'（C）/ Missing '\0' in C：C 字串靠 '\0' 標記結尾。少了它，印出來會多出亂碼。我們配置了 wordsSize + 1 並手動補上結尾。Forgetting the terminator leads to garbage past the string; we allocate one extra byte and set it.
• 索引算錯 / Wrong index：權重用 weights[c - 'a']，不是 weights[c]。直接用 c 會落在 ASCII 97 以上而越界。Use c - 'a', not c itself, or you read out of bounds.
• 取餘數的時機 / When to take %：對「總和」取一次 26 餘數即可，不需對每個字元取餘。最大總和 = 10 × 100 = 1000，遠在 int 範圍內，不會溢位。Take % 26 once on the final sum; the max sum is 1000, well within int, so no overflow worries.
• 單一字母單字 / Single-letter words：像 ["a","b","c"] 也適用同一套邏輯，內層迴圈只跑一次，無需特判。Single-character words need no special case; the inner loop simply runs once.