leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0097.cpp (728B)

      1 class Solution {
      2     short int dp[101][101];
      3     bool rec(const string &s1, const string &s2, const string &s3, int i = 0, int j = 0, int k = 0) {
      4         if (k == s3.size()) return true;
      5         if (dp[i][j] != -1) return dp[i][j];
      6 
      7         if (i != s1.size() && s1[i] == s3[k] && rec(s1, s2, s3, i + 1, j, k + 1)) return dp[i][j] = true;
      8 
      9         if (j != s2.size() && s2[j] == s3[k] && rec(s1, s2, s3, i, j + 1, k + 1)) return dp[i][j] = true;
     10 
     11         return dp[i][j] = false;
     12     }
     13 
     14   public:
     15     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     16     bool isInterleave(const string &s1, const string &s2, const string &s3) {
     17         if (s1.size() + s2.size() != s3.size()) return false;
     18         return rec(s1, s2, s3);
     19     }
     20 };