字符串匹配与编辑

def word_break(s: str, words: list[str]) -> bool:
    """Can s be cut into dictionary words, each usable any number of times? (LC 139)"""
    vocab = set(words)
    longest = max(map(len, words), default=0)
    ok = [True] + [False] * len(s)  # ok[i]: the prefix s[:i] can be cut
    for i in range(1, len(s) + 1):
        for j in range(max(0, i - longest), i):  # the last word is s[j:i]
            if ok[j] and s[j:i] in vocab:
                ok[i] = True
                break
    return ok[len(s)]

// Can s be cut into dictionary words, each usable any number of times? (LC 139)
bool wordBreak(const string& s, const vector<string>& words) {
    unordered_set<string> vocab(words.begin(), words.end());
    size_t longest = 0;
    for (auto& w : words) longest = max(longest, w.size());
    int n = s.size();
    vector<bool> ok(n + 1, false);  // ok[i]: the prefix s[0, i) can be cut
    ok[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = max(0, i - (int)longest); j < i && !ok[i]; j++)  // the last word is s[j, i)
            ok[i] = ok[j] && vocab.count(s.substr(j, i - j));
    return ok[n];
}

class Solution {
    // Can s be cut into dictionary words, each usable any number of times? (LC 139)
    boolean wordBreak(String s, List<String> words) {
        Set<String> vocab = new HashSet<>(words);
        int longest = 0;
        for (String w : words) longest = Math.max(longest, w.length());
        int n = s.length();
        boolean[] ok = new boolean[n + 1]; // ok[i]: the prefix s[0, i) can be cut
        ok[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = Math.max(0, i - longest); j < i && !ok[i]; j++) // the last word is s[j, i)
                ok[i] = ok[j] && vocab.contains(s.substring(j, i));
        return ok[n];
    }
}

// wordBreak reports whether s can be cut into dictionary words, each usable any number of times.
func wordBreak(s string, words []string) bool {
	vocab := map[string]bool{}
	longest := 0
	for _, w := range words {
		vocab[w] = true
		longest = max(longest, len(w))
	}
	ok := make([]bool, len(s)+1) // ok[i]: the prefix s[:i] can be cut
	ok[0] = true
	for i := 1; i <= len(s); i++ {
		for j := max(0, i-longest); j < i && !ok[i]; j++ { // the last word is s[j:i]
			ok[i] = ok[j] && vocab[s[j:i]]
		}
	}
	return ok[len(s)]
}

def num_distinct(s: str, t: str) -> int:
    """How many times t occurs in s as a subsequence (LC 115)."""
    dp = [1] + [0] * len(t)  # dp[j]: ways the part of s read so far forms t[:j]
    for c in s:
        for j in range(len(t), 0, -1):  # backwards: this c is used at most once per match
            if t[j - 1] == c:
                dp[j] += dp[j - 1]
    return dp[len(t)]

// How many times t occurs in s as a subsequence (LC 115).
unsigned long long numDistinct(const string& s, const string& t) {
    vector<unsigned long long> dp(t.size() + 1, 0);  // dp[j]: ways the part of s read so far forms t[0, j)
    dp[0] = 1;
    for (char c : s)
        for (size_t j = t.size(); j >= 1; j--)  // backwards: this c is used at most once per match
            if (t[j - 1] == c) dp[j] += dp[j - 1];
    return dp[t.size()];
}

class Solution {
    // How many times t occurs in s as a subsequence (LC 115).
    long numDistinct(String s, String t) {
        long[] dp = new long[t.length() + 1]; // dp[j]: ways the part of s read so far forms t[0, j)
        dp[0] = 1;
        for (char c : s.toCharArray())
            for (int j = t.length(); j >= 1; j--) // backwards: this c is used at most once per match
                if (t.charAt(j - 1) == c) dp[j] += dp[j - 1];
        return dp[t.length()];
    }
}

// numDistinct returns how many times t occurs in s as a subsequence (LC 115).
func numDistinct(s, t string) int {
	dp := make([]int, len(t)+1) // dp[j]: ways the part of s read so far forms t[:j]
	dp[0] = 1
	for i := 0; i < len(s); i++ {
		for j := len(t); j >= 1; j-- { // backwards: this character is used at most once per match
			if t[j-1] == s[i] {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[len(t)]
}