2707. 字符串中的额外字符

2707. 字符串中的额外字符

• 难度: medium
• 原始链接: https://leetcode.cn/problems/extra-characters-in-a-string
• 标签: 动态规划, 前缀树

解法一: 动态规划

java

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i] + 1;
            for (String word : dictionary) {
                if (this.isSameFromLast(s, i, word)) {
                    dp[i + 1] = Math.min(dp[i + 1], dp[i - word.length() + 1]);
                }
            }
        }
        return dp[n];
    }

    private boolean isSameFromLast(String str, int endIndex, String subStr) {
        int n1 = str.length();
        int n2 = subStr.length();
        if (n2 > endIndex + 1) {
            return false;
        }
        int i = endIndex;
        int j = n2 - 1;
        while (j >= 0) {
            if (str.charAt(i) != subStr.charAt(j)) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }

}

解法二: 前缀树

java

class Solution {

    public static class Trie {

        private Trie[] tries;

        private boolean isEnd;

        public Trie() {
            this.tries = new Trie[26];
            this.isEnd = false;
        }

        public void insert(String word) {
            int n = word.length();
            Trie trie = this;
            for (int i = 0; i < n; i++) {
                int j = word.charAt(i) - 'a';
                if (trie.tries[j] == null) {
                    trie.tries[j] = new Trie();
                }
                trie = trie.tries[j];
            }
            trie.isEnd = true;
        }

        public Trie track(char ch) {
            return tries[ch - 'a'];
        }

        public boolean isEnd() {
            return isEnd;
        }

    }

    public int minExtraChar(String s, String[] dictionary) {
        Trie root = new Trie();
        for (String word : dictionary) {
            StringBuilder sb = new StringBuilder(word);
            root.insert(sb.reverse().toString());
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i] + 1;
            Trie trie = root;
            for (int j = i; j >= 0; j--) {
                trie = trie.track(s.charAt(j));
                if (trie == null) {
                    break;
                }
                if (trie.isEnd()) {
                    dp[i + 1] = Math.min(dp[i + 1], dp[j]);
                }
            }
        }
        return dp[n];
    }

}