什么时候该算法破字的复杂性？ （动态规划）

问题描述

 公共类解决方案{
    公开名单＆LT;字符串＆GT; wordBreak（字符串S，集＆LT;字符串＆GT;字典）{
        名单＆LT;字符串＆GT;名单=新的ArrayList＆LT;字符串＆GT;（）;

        //输入检查。
        如果（S == NULL || s.length（）== 0 ||
            字典== NULL || dict.size（）== 0）返回目录;

        INT的len = s.length（）;

        //备忘录[i]的记录，
        //我们是否切断指数我，就可以得到结果之一。
        布尔备忘录[] =新的布尔[LEN]
        的for（int i = 0; I＆LT; LEN;我++）备注[I] = TRUE;

        StringBuilder的tmpStrBuilder =新的StringBuilder（）;
        助手（S，0，tmpStrBuilder，字典，列表，备忘录）;

        返回列表;
    }

    私人无效帮手（的String，诠释开始，StringBuilder的tmpStrBuilder，
                        设置＆LT;字符串＆GT;字典，列表和LT;字符串＆GT;列表中，布尔[]备忘录）{

        //基本情况。
        如果（开始＆gt; = s.length（））{
            list.add（tmpStrBuilder.toString（）修剪（））;
            返回;
        }

        INT listSizeBeforeRecursion = 0;
        的for（int i =启动; I＆LT; s.length（）;我++）{
            如果（备注[I] ==假）继续;

            字符串CURR = s.substring（启动，I + 1）;
            如果继续（dict.contains（CURR）！）;

            //有一个尝试。
            tmpStrBuilder.append（CURR）;
            tmpStrBuilder.append（）;

            //做递归。
            listSizeBeforeRecursion =则为list.size（）;
            助手（S，I + 1，tmpStrBuilder，字典，列表，备忘录）;

            如果（则为list.size（）== listSizeBeforeRecursion）备注[I] = FALSE;

            //回滚。
            tmpStrBuilder.setLength（tmpStrBuilder.length（） -  curr.length（） -  1）;
        }
    }
}
 

解决方案

通过DP：

时间：O（N * M） N - 字符串大小 米 - 字典大小

内存：O（N）

请参阅我的答案在这里，用code例如：

Dynamic编程 - 字歇

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);
        }
    }
}

解决方案

With DP:

Time: O(N*M) N - string size M - dict size

Memory: O(N)

See my answer here, with code example:

Dynamic Programming - Word Break

这篇关于什么时候该算法破字的复杂性？ （动态规划）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！