algorithm - 在字符列表中查找单词

我有一个在线自学家庭作业总结要做：
在字符列表中查找单词。

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上尝试但是，我希望这可以通过动态编程来解决。我不知道在哪里可以将输入保存到缓存/内存中以便再次使用。

最佳答案

为什么选择动态编程您要查找字符列表中是否存在输入字我会给你一个简单有效的方法。

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）。

关于algorithm - 在字符列表中查找单词，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43959826/