解開字符串

-4

如何使用提供的單詞列表解開字符串。解開字符串

例如：

List of words in Dictionary: 

Hi 
Hello 
Welcome 
to 
Stack 
Overflow 

Input String: 

WelcometoStackOverflow 

Output must be (with space added): 

Welcome to Stack Overflow

對於列表中不存在的話，NULL應打印。

Input String: 

StackOverflowWelcomeYou 

Output must be: 

NULL

任何建議或想法如何實現......？

來源

2013-07-20 Gokul Nath KP

首先，請決定的語言。其次，請親自嘗試自己做這件事併發布你所擁有的代碼，以證明一些努力。 – NPE

三，更準確地描述問題。 – juanchopanza

可以輸入假設爲駱駝情況（以大寫字母開頭）。 – anubhava

最大的挑戰是如何分解輸入字符串，所有的答案/評論將基於一些假設，直到OP提供更多細節。

在這個答案假設是輸入是一個駱駝大小寫字符串，第一個字母大寫。

public class CheckDict { 
    static Set<String> dict = new HashSet<String>(Arrays.asList(new String[] 
           {"Hi", "Hello", "Welcome", "To", "Stack", "Overflow"})); 

    public static void main(String[] args) { 
     System.out.println("Test 1: " + findDict("WelcomeToStackOverflow")); 
     System.out.println("Test 2: " + findDict("StackOverflowWelcomeYou")); 
    } 

    static String findDict(String str) { 
     // split the string when we encounter an upper case letter except at start 
     String[] arr = str.split("(?<!^)(?=[A-Z])"); 
     StringBuilder output = new StringBuilder(arr[0]); 
     for (int i=1; i< arr.length; i++) { 
      if (!dict.contains(arr[i])) 
       return null; 
      else 
       output.append(' ').append(arr[i]); 
     } 
     return output.toString(); 
    } 
}

OUTPUT：

Test 1: Welcome To Stack Overflow 
Test 2: null

來源

2013-07-20 07:51:56 anubhava

這裏是我將採取的方法來解決算法。

1）負載在字典成哈希映射結構ammortized恆定時間的查找，或轉換成用於對數時間的有序地圖查找

2）iterater通過可能的子串[0，I]，直到匹配在字典中找到

a）如發現匹配remove從在一個ArrayList結構中的輸入字符串和存儲該字用於報告最後的答案

b）如沒有發現匹配或i等於到字符串報告大小null

3）遍歷字符串的列表並打印空格分隔的列表

根據查找時間，我們稱之爲L，該算法應該採用O（n * L），其中n是字符數輸入字符串。如果查找需要分段恆定時間，例如哈希映射，那麼它將是O（n），否則可以在O（n log D）中完成。其中D是字典的大小。

來源

2013-07-20 07:17:42 pippin1289

回答

相關問題