Try   HackMD

LeetCode 2416. Sum of Prefix Scores of Strings

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

題目大意

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

我們定義字串 term 的分數為滿足 termwords[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 的方式來解題

假設有兩個字串

si1
si
他們在字典順序上是相鄰的
dp[i,j]
表示到第
j
個字母為止
si1
si
的共同前綴長

則我們可以得到:

dp[i,j]={0if si1[j]si[j]dp[i1,j]+1if si1[j]=si[j]

但這樣就算把所有 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 ,而且我們需要花時間建立,之後才能再遍歷一次字串算成績
這樣的做法屬於依賴資料結構的特性

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →