时间戳

首页 > 解决方案 > 如何在 stringPattern 值birdantantcatbirdcat 中获取字符串结果

java - 如何在 stringPattern 值birdantantcatbirdcat 中获取字符串结果

问题描述

我有 dataDic 是一个数组 {"ant","bird","cat"}

dataDic 是我想在 stringPattern 上搜索的单词数组

我想使用 dataDic 从 stringPattern = birdantantcatbirdcat 获取单词结果

例 1。dataDic = {"ant","bird","cat"} 答案是 {bird,ant,ant,cat,bird,cat} Ex2。dataDic = {"ant","cat"} 答案是 {ant,ant,cat,cat}

这是我的代码`private static String stringTest="birdantantcatbirdcat"; 私有静态列表 dicListWord；私有静态 ListresultString = new ArrayList<>();

public static void main(String[] args) {

    dicListWord = new ArrayList<>();
    dicListWord.add("ant");
    dicListWord.add("bird");
    dicListWord.add("cat");
    String[] data = stringTest.split("");

    for (String dataDic:dicListWord) {
        String [] wordList = dataDic.split("");
        String foundWord = "";
        for (String charTec:data) {
            for (String dicWord:wordList) {
                if(charTec.equals(dicWord)){
                    foundWord = foundWord.concat(charTec);
                    if(dataDic.equals(foundWord)){
                        resultString.add(foundWord);
                        foundWord = "";
                    }
                }
            }
        }
    }

    for (String w1:data) {
        for (String result:resultString) {
                System.out.println(result);
        }
    }
}`

///////////////////////////////////////// /////////////////////////

我运行的结果是

{蚂蚁，蚂蚁，鸟，鸟，蚂蚁，蚂蚁，鸟，鸟，蚂蚁，蚂蚁，鸟，鸟，蚂蚁，蚂蚁，鸟，鸟，蚂蚁，蚁鸟，鸟，蚂蚁，鸟，鸟，蚂蚁，蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟,蚂蚁,蚂蚁,鸟,鸟}

标签： javaarraysarraylist

解决方案

这是一个分词问题，可以使用深度优先搜索来解决。但是明智的做法是先检查给定的字符串模式是否可破坏，以便在我们给出的长字符串模式与字典中的任何单词都不匹配的情况下获得更好的运行时间。

public class P00140_Word_Break_II {
public static void main(String[] args) {
    String input = "catsanddog";
    List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
    P00140_Word_Break_II solution = new P00140_Word_Break_II();
    List<String> results = solution.wordBreak(input, wordDict);
    System.out.println(results);
    String input1 = "birdantantcatbirdcat";
    List<String> wordDict1 = Arrays.asList("ant","bird","cat");
    List<String> results1 = solution.wordBreak(input1, wordDict1);
    System.out.println(results1);

}

public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    List<String> result = new ArrayList<>();
    if (s == null || s.length() == 0 || !isbreakable(s, dict)) {
        return result;
    }
    helper(s, 0, new StringBuilder(), dict, result);
    return result;
}

public void helper(String s, int start, StringBuilder item, Set<String> dict, List<String> results) {

    if (start >= s.length()) {
        results.add(item.toString());
        return;
    }

    if (start != 0) {
        item.append(" ");
    }

    for (int i = start; i < s.length(); i++) {
        String temp = s.substring(start, i + 1);
        if (dict.contains(temp)) {
            item.append(temp);
            helper(s , i+1 , item , dict , results);
            item.delete(item.length() + start - i - 1 , item.length());
        }
    }
    if(start!=0) item.deleteCharAt(item.length()-1);
}

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

}

推荐阅读