如果一个字由两个有效字 [英] If a word is made up of two valid words

问题描述

由于字典发现，如果给定的话可以在字典中两个词进行。对于如。给予报纸你必须要找到它是否可以用两个词来进行。 （新闻和纸在这种情况下）。我唯一​​能想到的是，从年初开始，并检查是否当前字符串是一个单词。在这种情况下检查N，东北，新，新闻.....检查剩余的部分，如果当前字符串是一个有效的字。

Given a dictionary find out if given word can be made by two words in dictionary. For eg. given "newspaper" you have to find if it can be made by two words. (news and paper in this case). Only thing i can think of is starting from beginning and checking if current string is a word. In this case checking n, ne, new, news..... check for the remaining part if current string is a valid word.

另外，你如何概括它的K（意味着如果字是由K字）？有什么想法？

Also how do you generalize it for k(means if a word is made up of k words) ? Any thoughts?

推荐答案

对于两个词的情况下，这个问题可以通过只考虑分拆字一分为二，然后选中各占一半，看看它是一切可能的办法解决一个有效的字。如果输入的字符串长度为n，则有分割字符串的唯一O（n）的方式不同。如果存储在支持快速查找结构的字符串（例如，一个线索，或哈希表）。

For the case with two words, the problem can be solved by just considering all possible ways of splitting the word into two, then checking each half to see if it's a valid word. If the input string has length n, then there are only O(n) different ways of splitting the string. If you store the strings in a structure supporting fast lookup (say, a trie, or hash table).

更有趣的情况是，当你有K> 2个字的单词拆分成。对于这一点，我们可以用一个非常优雅的递归公式：

The more interesting case is when you have k > 2 words to split the word into. For this, we can use a really elegant recursive formulation:

一个字可以分割成k个字，如果它可以被分成一个字，接着一个字可分裂为k - 1词语

A word can be split into k words if it can be split into a word followed by a word splittable into k - 1 words.

递归基本情况是，一个字可以分为零的话，只有当它是空字符串，这是平凡的真实。

The recursive base case would be that a word can be split into zero words only if it's the empty string, which is trivially true.

要使用递归的洞察力，我们会考虑这个词的所有可能分裂成两个部分修改原有的算法。一旦我们有了该分割，我们可以检查是否拆分的第一部分是一个字，如果分割的第二部分可分开被分解为k - 1字。作为优化，我们不递归上所有可能的分割，而是仅仅对那些在我们知道的第一个字是有效的。下面是一些示例code用Java编写的：

To use this recursive insight, we'll modify the original algorithm by considering all possible splits of the word into two parts. Once we have that split, we can check if the first part of the split is a word and if the second part of the split can be broken apart into k - 1 words. As an optimization, we don't recurse on all possible splits, but rather just on those where we know the first word is valid. Here's some sample code written in Java:

 public static boolean isSplittable(String word, int k, Set<String> dictionary) {
     /* Base case: If the string is empty, we can only split into k words and vice-
      * versa.
      */
     if (word.isEmpty() || k == 0)
         return word.isEmpty() && k == 0;

     /* Generate all possible non-empty splits of the word into two parts, recursing on
      * problems where the first word is known to be valid.
      *
      * This loop is structured so that we always try pulling off at least one letter
      * from the input string so that we don't try splitting the word into k pieces
      * of which some are empty.
      */
     for (int i = 1; i <= word.length(); ++i) {
          String first = word.substring(0, i), last = word.substring(i);

          if (dictionary.contains(first) &&
              isSplittable(last, k - 1, dictionary)
              return true;
     }

     /* If we're here, then no possible split works in this case and we should signal
      * that no solution exists.
      */
     return false;
 }

 }

这code，在最坏的情况下，运行时间为O（n ^K ），因为它试图生成字符串的所有可能的分区为k的不同部分。当然，它不可能打这个最坏情况下的行为，因为最有可能拆分最终不会形成任何话。

This code, in the worst case, runs in time O(n^k) because it tries to generate all possible partitions of the string into k different pieces. Of course, it's unlikely to hit this worst-case behavior because most possible splits won't end up forming any words.

这篇关于如果一个字由两个有效字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！