using namespace std;
#include <iostream>
#include <vector>
#include <string>

// Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,
// determine if s can be segmented into a space-separated sequence of one or more dictionary words.

class SpaceSeparatedSequence
{
public:
  static bool canBeSeparated(string s, vector<string> wordDict)
  {
    // Start of the test word
    int index1 = 0;
    // End of the test word
    int index2 = 0 + 1;
    // Until we have reached the end of the word
    while (index1 < s.size() - 1)
    {
      // If we haven't foudn a word for teh rest of rht string, return false
      if (index2 >= s.size()) {
        return false;
      }
      // The substring to check
      string testString = s.substr(index1, index2 + 1 - index1);
      //Check each word in the dictionary
      for (auto dictWord : wordDict)
      {
        // If the substring is in the dictionary
        if (dictWord == testString)
        {
          // Move the end of the string
          index1 = index2 + 1;
          index2 = index1 + 1;
          break;
        }
      }
      index2++;
    }
    if (index1 == s.size())
    {
      return true;
    }
    else
    {
      return false;
    }
  }
};

int main()
{
  // One test where the program should succeed
  string input = "testingthisstring";
  vector<string> wordDict = {"testing", "hello", "world", "this", "string"};
  cout << SpaceSeparatedSequence::canBeSeparated(input, wordDict) << endl;

  // One test where it should succeed out of order
  input = "worldhello";
  wordDict = {"testing", "hello", "world", "this", "string"};
  cout << SpaceSeparatedSequence::canBeSeparated(input, wordDict) << endl;

  // One test where it should fail
  input = "trytotestthisstring";
  wordDict = {"testing", "hello", "world", "this", "string"};
  cout << SpaceSeparatedSequence::canBeSeparated(input, wordDict) << endl;
}