2

単語区切り(動的プログラミングを使用: Top->Down)
文字列 s と単語 dict の辞書が与えられた場合、s にスペースを追加して、各単語が有効な辞書単語である文を作成します。

そのような可能な文をすべて返します。

たとえば、指定された
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

解決策は【「猫と犬」、「猫砂犬」】です。

質問：

  • 時間の複雑さ ?
  • 空間の複雑さ ?

個人的に私は思います、

  • 時間計算量 = O(n!)、動的計画法なし、n は与えられた文字列の長さ、
  • スペースの複雑さ = O(n)。

困惑：

  • 動的計画法で時間計算量を把握できません。
  • 上記のスペースの複雑さは正しくないようです。

コード[Java]

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> list = new ArrayList<String>();

        // Input checking.
        if (s == null || s.length() == 0 || 
            dict == null || dict.size() == 0) return list;

        int len = s.length();

        // memo[i] is recording,
        // whether we cut at index "i", can get one of the result.
        boolean memo[] = new boolean[len];
        for (int i = 0; i < len; i ++) memo[i] = true;

        StringBuilder tmpStrBuilder = new StringBuilder();
        helper(s, 0, tmpStrBuilder, dict, list, memo);

        return list;
    }

    private void helper(String s, int start, StringBuilder tmpStrBuilder,
                        Set<String> dict, List<String> list, boolean[] memo) {

        // Base case.
        if (start >= s.length()) {
            list.add(tmpStrBuilder.toString().trim());
            return;
        }

        int listSizeBeforeRecursion = 0;
        for (int i = start; i < s.length(); i ++) {
            if (memo[i] == false) continue;

            String curr = s.substring(start, i + 1);
            if (!dict.contains(curr)) continue;

            // Have a try.
            tmpStrBuilder.append(curr);
            tmpStrBuilder.append(" ");

            // Do recursion.
            listSizeBeforeRecursion = list.size();
            helper(s, i + 1, tmpStrBuilder, dict, list, memo);

            if (list.size() == listSizeBeforeRecursion) memo[i] = false;

            // Roll back.
            tmpStrBuilder.setLength(tmpStrBuilder.length() - curr.length() - 1);
        }
    }
}
4

2 に答える 2

2

DP の場合:

時間: O(N*M) N - 文字列サイズ M - dict サイズ

メモリ: O(N)

コード例とともに、ここで私の答えを参照してください。

動的計画法 - ワード ブレーク

于 2014-08-11T01:52:16.817 に答える
0

動的問題です。

2つのことを維持できます。

1 DP[i] は、文字列が i 番目の文字にある場合、それを切り取る方法が dp[i] あることを意味します。

2 ベクトル < int> pre[i] は、前の位置が現在の i 番目の位置に到達できることを意味します (サイズは DP[i] でなければなりません)。

時間は O(n*m)

まず、i は [0,n) にあります。

次に、[0,i) で j を見つけます。その部分文字列 (j+1,i) は有効です。

検証は事前に計算できます。したがって、時間は O(n*m) であり、 vector < int> pre[i] を使用して、必要なすべての切断ソリューションを取得できます。

于 2014-08-11T04:41:11.333 に答える