查找字符列表中的單詞

我有一個在線自學功課總和要做：查找單詞列表中的單詞。查找字符列表中的單詞

eg Input: COOL 
List of characters: {A,B,C,O,L,M,O,L,F} return true 
Input : Book 
List of characters: {A,B,C,O,L,M,O,L,F} return false (as K is not present). 
Note: C found at index 2, then O should be found at index > 2 (Linear searching, search from left to right). 

I could think of two solutions, both brute force. 
1. Using Brute force approach to get the output 
2. Using Recursion (not sure if this approach is right, however, I am expected to solve it using dynamic programming).

不是動態規劃方面的專家，請耐心等待。的解決方案，我想出了：

public boolean found(final String input,int n, boolean isFound, int a, String words) { 

    if(n == input.length) { 
     return isFound; 
    } 

char charValue = input.charAt(n); 

for(int i = a; i<words.length-1; i++) { 

    if(charValue == words.charAt[i]) { 
     isFound = true; 
    return found(input, n+1, true, i+1; words); 
    }else { 
    isFound = false; 
    } 
} 

    return isFound; 
}

我不知道這個解決方案有效，需要嘗試它的IDE。不過，我期待這一點可以通過動態編程來解決。我沒有看到我可以將輸入保存在緩存/內存中以便再次使用。

來源

2017-05-14 LifeStartsAtHelloWorld

爲什麼要進行動態編程？您想要查找輸入單詞是否存在於字符列表中。我會給你一個簡單而有效的方法。

bool is_word_present(string word, vector<char> word_list){ 
    int word_index = 0; 
    int word_list_size = word_list.size(); 
    int word_len = word.length(); 
    for(int i = 0; i < word_list_size && word_index < word_len; i++){ 
     if(word_list[i] == word[word_index]){ 
      word_index++; 
     } 
    } 
    return word_index == word_len; 
}

的問題有java代碼，我在這裏給C++代碼。但是，當你對問題的算法部分感興趣時無關緊要。而且代碼是不言自明的。

時間複雜度：O（n）其中n是字符列表中元素的數量。

空間複雜度：O（1）。

來源

2017-05-14 09:18:19

感謝您的解決方案。我正在參加Udemy課程，在動態編程部分，講師提到這是一個家庭作業總和。 – LifeStartsAtHelloWorld

將文件列表（例如來自The Oxford Dictionary）從文件加載到列表中。

當您通過它時，您將從此列表中刪除單詞，因此從最後一個索引（長度爲1）循環到第一個。

在該循環內有一個內部循環，遍歷單詞中的每個字母。如果當前字符不在允許字符列表中，則從列表中刪除單詞並跳出內部循環。

我不認爲這是一個動態編程問題。如果你正在檢查一本書中的所有單詞，那麼你會將你檢查的每一個單詞存儲在一個通過散列集合或一個失敗散列集合中，這樣你可以在處理每個字母之前查看它（例如，以前結果的內存緩存以便學習）。在這種情況下，它不會變得更快，它可能會減慢速度，因爲創建字符串的散列需要每個字符都被讀取。

在C＃中，您可以通過單個LINQ語句輕鬆實現此目的。

void Main() 
{ 
    string[] wordsToProcess = new string[] { "one", "two", "three", "bad", "cat", "dog" }; 
    char[] charactersToAllow = new char[] { 'a', 'b', 'c', 'd', 'e', 't', 'o', 'g' }; 
    List<string> qualifyingWords = 
     wordsToProcess 
      .Where(w => w.All(c => charactersToAllow.Contains(c))) 
      .ToList(); 
    qualifyingWords.ForEach(Console.WriteLine); 
}

來源

2017-05-14 09:45:39

感謝您的解決方案。我正在參加Udemy課程，在動態編程部分，講師提到這是一個家庭作業總和。即使我想知道，這怎麼可能是DP總和。我感謝您的幫助。 – LifeStartsAtHelloWorld

如果在課程中向您提出了建議的解決方案，請回過頭來張貼，這樣我們就可以看到您的教師的想法。 –

查找字符列表中的單詞

回答

相關問題