leetcode139：单词拆分

题目链接

leetcode

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

/*
    状态表示：
        dp[i] 表示字符串 s[0, i] 的前 i 个字符是否可以被 wordDict 拼出。
    状态计算：
        对于字符串 s 的每个位置 i，需要检查所有可能的拆分点 j (0 <= j <= i - 1)。
        若 dp[j] 为 true，说明字符串 s 的前 j 个字符可以被拆分。
        若 s.substr(j, i - j) 是字典中的单词，则 dp[i] = true。

    时间复杂度：O(n^2*m)
        其中 n 是字符串 s 的长度，m 是字典 wordDict 的大小。
        状态计算：O(n^2)，数组中查找的时间复杂度为 O(m)，        
        总时间复杂度为 O(n^2*m)。
    空间复杂度：O(n)
        数组的大小为 O(n)。
*/
class Solution_0 {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> f(n + 1, false);
        f[0] = true;
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j < i; j ++) {
                auto it = find(wordDict.begin(), wordDict.end(), s.substr(j, i - j));
                if (f[j] && wordDict.end() != it) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[n];
    }
};

/*
    优化时间复杂度：使用 unordered_set 存储字典中的单词
    查找操作的时间复杂度降低到平均 O(1)。

    时间复杂度：O(n^2)
        其中 n 是字符串 s 的长度，m 是字典 wordDict 的大小。
        字典转换为哈希表：O(m)，状态计算：O(n^2)，
        总时间复杂度为 O(n^2)。
    空间复杂度：O(n + m)
        数组的大小为 O(n)，哈希表的大小为 O(m)，
        总空间复杂度为 O(n + m)。
*/
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordDictSet(wordDict.begin(), wordDict.end());
        int n = s.length();
        vector<bool> f(n + 1, false);
        f[0] = true;
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j < i; j ++) {
                // if (f[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                if (f[j] && wordDictSet.count(s.substr(j, i - j))) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[n];
    }
};

int main() {
    Solution solution;
    vector<pair<string, vector<string>>> test_cases = {
        {"leetcode", {"leet", "code"}},
        {"applepenapple", {"apple", "pen"}},
        {"catsandog", {"cats", "dog", "sand", "and", "cat"}}
    };

    for (const auto& test_case : test_cases) {
        string s = test_case.first;
        vector<string> wordDict(test_case.second.begin(), test_case.second.end());
        bool result = solution.wordBreak(s, wordDict);
        cout << "The string is: " << s 
            << ", result: " << (result ? "true" : "false") << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   动态规划：
       定义状态 dp[i] 表示字符串 s 的前 i 个字符是否可以被 wordDict 中的单词拼接而成。
       初始化 dp[0] = true，因为空字符串可以被拼接。
       对于每个位置 i，遍历所有可能的 j（0 <= j < i），检查：
           dp[j] 是否为 true。
           子串 s[j:i] 是否在 wordDict 中。
       如果满足条件，则 dp[i] = true。
   哈希表：
       使用哈希表存储 wordDict 中的单词，方便快速查找。

    时间复杂度：O(n^2)
        其中 n 是字符串 s 的长度。
        外层循环遍历字符串的每个位置，内层循环遍历所有可能的 j，时间复杂度为 O(n^2)。
    空间复杂度：O(n+m)
        使用了一个大小为 n+1 的动态规划数组 dp，空间复杂度为 O(n)。
        使用了一个哈希表存储 wordDict，空间复杂度为 O(m)，其中 m 是 wordDict 的长度。
        因此，空间复杂度为 O(n+m)。
*/
// wordBreak 判断字符串 s 是否可以由 wordDict 中的单词拼接而成
func wordBreak(s string, wordDict []string) bool {
	// 将 wordDict 转换为哈希表，方便快速查找
	wordSet := make(map[string]bool)
	for _, word := range wordDict {
		wordSet[word] = true
	}

	n := len(s)
	dp := make([]bool, n + 1)
	dp[0] = true // 空字符串可以被拼接
    
	for i := 1; i <= n; i ++ {
		for j := 0; j < i; j ++ {
			if dp[j] && wordSet[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}

	return dp[n]
}

func main() {
	// 测试用例
	testCases := []struct {
		s        string
		wordDict []string
		expected bool
	}{
		{
			s:        "leetcode",
			wordDict: []string{"leet", "code"},
			expected: true,
		},
		{
			s:        "applepenapple",
			wordDict: []string{"apple", "pen"},
			expected: true,
		},
		{
			s:        "catsandog",
			wordDict: []string{"cats", "dog", "sand", "and", "cat"},
			expected: false,
		},
	}

	for i, tc := range testCases {
		result := wordBreak(tc.s, tc.wordDict)
		fmt.Printf("Test Case %d, Input: s = %q, wordDict = %v\n", i+1, tc.s, tc.wordDict)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}