题目链接：实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

方法一：前缀树

class Trie {
public:
    bool isEnd;
    Trie* next[26];
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    void insert(string word) {
        Trie* node = this;
        for (char c : word) {
            if (node->next[c-'a'] == NULL) {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = this;
        for (char c : word) {
            node = node->next[c-'a'];
            if (node == NULL) {
                return false;
            }
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c : prefix) {
            node = node->next[c-'a'];
            if (node == NULL) {
                return false;
            }
        }
        return true;
    }
};
/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

题目链接：课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

方法一：DFS

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> f(numCourses,0);
        vector<vector<int>> rel(numCourses,vector<int>{});
        for (auto x : prerequisites) {
            f[x[0]]++;
            rel[x[1]].push_back(x[0]);
        }
        queue<int> q;
        for (int i = 0;i < numCourses;i++) {
            if (f[i] == 0) {
                q.push(i);
            }
        }

        int les = 0;
        while (q.size()) {
            les++;
            int fi = q.front();
            q.pop();
            for (auto x : rel[fi]) {
                f[x]--;
                if (f[x] == 0) {
                    q.push(x);
                }
            }
        }
        return les == numCourses;
    }
};

题目链接：编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

方法一：二维数组+动态规划

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < dp[0].size(); j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].size(); j++) {
                // dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                // if (word1[i - 1] == word2[j - 1]) {
                //     dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                // }
                dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp.back().back();
    }
};

题目链接：最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

方法一：二维数组+动态规划

class Solution {
public:
    int f[1010][1010];
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                f[i+1][j+1] = text1[i] == text2[j] ? f[i][j] + 1 : max(f[i][j+1],f[i+1][j]); 
            }
        }
        return f[n][m];
    }
};

题目链接：最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

方法一：中心扩散

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int bestL = 0, bestLen = 1;

    for (int i = 0; i < n; ++i) {
        int l = i - 1, r = i + 1;

        // 吃掉与中心相同的连续字符（处理 "aaaa" 这类）
        while (l >= 0 && s[l] == s[i]) --l;
        while (r < n && s[r] == s[i]) ++r;

        // 再向两边扩展
        while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; }

        int len = r - l - 1;
        int start = l + 1;
        if (len > bestLen) { bestLen = len; bestL = start; }
    }
    return s.substr(bestL, bestLen);
}

方法一优化

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int bestL = 0, bestLen = 1;

    for (int i = 0; i < n; ) {
        int l = i, r = i;
        while (r + 1 < n && s[r + 1] == s[i]) ++r;  // 合并重复中心
        i = r + 1;                                  // 关键：跳到下一段

        // 扩展
        while (l - 1 >= 0 && r + 1 < n && s[l - 1] == s[r + 1]) { --l; ++r; }

        int len = r - l + 1;
        if (len > bestLen) { bestLen = len; bestL = l; }

        // 可选剪枝：如果剩余长度不足以超越 bestLen
        if ((n - i) * 2 + 1 <= bestLen) break;
    }
    return s.substr(bestL, bestLen);
}