ARTS-9-算法练习-动态规划之字符串匹配

66 阅读 0 评论 44 点赞

我是靠谱客的博主儒雅诺言，最近开发中收集的这篇文章主要介绍ARTS-9-算法练习-动态规划之字符串匹配，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

概述：
左耳朵耗子专栏《左耳听风》用户自发每周完成一个ARTS：

1.Algorithm：每周至少做一个 leetcode 的算法题

2.Review：阅读并点评至少一篇英文技术文章

3.Tip：学习至少一个技术技巧

4.Share：分享一篇有观点和思考的技术文章

Algorithm
题目概述：

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s ="leetcode",
dict =["leet", "code"].

Return true because"leetcode"can be segmented as"leet code".

代码：

package 算法部分.动态规划;

import java.util.HashSet;
import java.util.Set;

/**
 * Given a string s and a dictionary of words dict,
 * determine if s can be segmented into a space-separated
 * sequence of one or more dictionary words.
 * <p>
 * For example, given
 * s ="leetcode",
 * dict =["leet", "code"].
 * <p>
 * Return true because"leetcode"can be segmented as"leet code".
 *
 * @author idea
 * @data 2019/6/19
 */
public class Demo {


    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        boolean[] arrays = new boolean[len + 1];
        arrays[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (arrays[j] && dict.contains(s.substring(j,i))) {
                    arrays[i]=true;
                    break;
                }
            }
        }
        return arrays[len];
    }


    public static void main(String[] args) {
        Demo demo=new Demo();
        Set<String> set=new HashSet<>();
        set.add("id");
        set.add("eat");
        boolean result=demo.wordBreak("ideat",set);
        System.out.println(result);
    }
}

这段代码的核心思路是通过使用一个存储boolean类型的数组来进行判别是否可以进行词语分隔。假如说可以判别某个词组可以由多个其他的词组组成，那么就将其对应索引位置的布尔值变为true。最后如果尾部最后一个布尔值为true，则识别成功。