# LeetCode 2416. Sum of Prefix Scores of Strings

https://leetcode.com/problems/sum-of-prefix-scores-of-strings/description/

## 題目大意

給定一個大小為 `n` 的字串陣列 `words`，其中每個字串都是非空的

我們定義字串 `term` 的分數為滿足 `term` 是 `words[i]` 的前綴字串的字串數量

例如，若 `words = ["a", "ab", "abc", "cab"]`，則 `"ab"` 的分數是 2，因為 `"ab"` 是 `"ab"` 和 `"abc"` 的前綴字串

回傳一個大小為 `n` 的陣列 `answer`，其中 `answer[i]` 是 `words[i]` 的每個非空前綴字串的分數總和

注意：

1. 字串被認為是它自己的前綴字串
2. 字串只會有小寫字母

## 思考

### Algo 1

這題看到 prefix of string 我們多少應該會想到 Trie
沒錯，我們可以使用 Trie 的概念來解這題

不過我們沒有需要**查找一個詞**，我們只需要累計出他的分數就好

class TrieNode
{
public:
    array<TrieNode *, 26> children;
    int cnt;

    TrieNode() : cnt(0)
    {
        children.fill(nullptr);
    }
};

class Trie
{
public:
    Trie() : root(new TrieNode()) {}

    void insert(const string &word)
    {
        TrieNode *node = root;
        for (char c : word)
        {
            const int i = c - 'a';
            if (!node->children[i])
                node->children[i] = new TrieNode();

            node = node->children[i];
            ++node->cnt;
        }
    }

    int getScore(const string &word)
    {
        TrieNode *node = root;
        int score = 0;

        for (char c : word)
        {
            const int i = c - 'a';
            if (!node->children[i])
                break;

            node = node->children[i];
            score += node->cnt;
        }

        return score;
    }

private:
    TrieNode *root;
};

class Solution
{
public:
    vector<int> sumPrefixScores(vector<string> &words)
    {
        Trie trie;

        for (const auto &word : words)
        {
            trie.insert(word);
        }

        vector<int> ans;
        ans.reserve(words.size());
        for (const auto &word : words)
        {
            ans.emplace_back(trie.getScore(word));
        }

        return ans;
    }
};

### Algo 2

使用 Trie 能更便利我們聯想到解法
不過我們其實還能從中再得到一些啟發

Trie 做的其實可以理解成基於前綴的分類
那其實，我們依據字典順序做排序，不也是能達到分類嗎？

例如 `words = ["abc","ab","bc","b"]`
經過排序後應該會是 `sorted_words = ["ab", "abc", "b", "bc"]`
你會發現前綴有 `"ab"` 的字串會被排在一起

這就衍伸出第二種演算法
我們使用 DP 的方式來解題

假設有兩個字串 $s_{i-1}$ 跟 $s_i$ 他們在字典順序上是相鄰的
令 $dp[i,j]$ 表示到第 $j$ 個字母為止 $s_{i-1}$ 跟 $s_i$ 的共同前綴長

則我們可以得到：

$$
dp[i,j] =
\begin{cases}
0 &\text{if } s_{i-1}[j] \neq s_i[j] \\
dp[i-1,j] + 1 & \text{if } s_{i-1}[j] = s_i[j]
\end{cases}
$$

但這樣就算把所有 `j` 的情況都掃過一輪，我們仍未解決這個題目，需要反轉順序後再執行一遍上述檢查
簡單理解就是目前我們只有由前往後看，還需要由後往前看回來，得到的 `ans[i]` 才會是雙向互看的結果
否則會發現有些情況會漏算

最後不要忘了，**字串被認為是它自己的前綴字串** 😉

class Solution
{
public:
    vector<int> sumPrefixScores(vector<string> &words)
    {
        const int n = words.size();
        vector<int> ans(n);

        vector<pair<string, int>> wordPairs;
        for (int i = 0; i < n; ++i)
        {
            wordPairs.emplace_back(words[i], i);
        }

        sort(wordPairs.begin(), wordPairs.end());

        calculateScores(wordPairs, ans, n);

        reverse(wordPairs.begin(), wordPairs.end());
        calculateScores(wordPairs, ans, n);

        for (const auto &wp : wordPairs)
        {
            ans[wp.second] += wp.first.size();
        }

        return ans;
    }

private:
    void calculateScores(const vector<pair<string, int>> &wordPairs, vector<int> &ans, int n)
    {
        vector<int> dp(wordPairs.begin()->first.size());

        for (int i = 1; i < n; ++i)
        {
            const string &prev = wordPairs[i - 1].first;
            const string &curr = wordPairs[i].first;
            int idx = wordPairs[i].second;

            vector<int> ndp(curr.size());
            const int m = min(prev.size(), curr.size());

            for (int j = 0; j < m; ++j)
            {
                if (curr[j] != prev[j])
                    break;

                ndp[j] = dp[j] + 1;
                ans[idx] += ndp[j];
            }

            dp = move(ndp);
        }
    }
};

algo 2 本質上還是跟 algo 1 做類似的事情，卻換來了是時間空間上的節省
雖然比較不好懂，但以執行結果來說，algo 2 的成績明顯好很多

algo 1 的缺點很明顯，我們的資料結構不但會花更多的 Memory ，而且我們需要花時間建立，之後才能再遍歷一次字串算成績
這樣的做法屬於依賴資料結構的特性