arc065_a - Daydream
29 Nov 2020 — Tags: backtracking — URL- For position $i$, try all possible matches and backtrack if one doesn’t work.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int n;
string s, opts[4] = {"dream", "dreamer", "erase", "eraser"};
bool solve(int i)
{
if (i == n)
return true;
bool ans = false;
for (auto const &opt : opts)
{
int m = (int)(opt).size();
if (m + i <= n and s.substr(i, m) == opt)
ans = solve(i + m);
if (ans)
break;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
cin >> s;
n = (int)(s).size();
cout << (solve(0) ? "YES" : "NO") << endl;
return 0;
}