<commit_before>/*
 * Copyright (c) 2013 <NAME>.
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * @author	<NAME> <<EMAIL>>
 * @date		2013-1-8
 */

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

class Solution {
public:
  bool isInterleave(string s1, string s2, string s3) {
      int n1 = s1.size();
      int n2 = s2.size();
      int n3 = s3.size();
      if (n1 + n2 != n3) return false;
      vector<vector<bool> > d(n1 + 1, vector<bool>(n2 + 1, false));
      d[0][0] = true;
      for (int i = 0; i < n3; ++i) {
          for (int j = 0; j <= i && j <= n1; ++j) {
            if (d[j][i - j]) {
              if (j < n1 && s1[j] == s3[i]) {
                d[j + 1][i - j] = true;
              }
              if (i - j < n2 && s2[i - j] == s3[i]) {
                d[j][i - j + 1] = true;
              }
            }
          }
      }
      for (int j = 0; j <= n1; ++j) {
        if (d[j][n3 - j]) return true;
      }
      return false;
  }
};

#include "util.h"

int main(int argc, char **argv) {
  std::cout << "------" << argv[0] << "------" << std::endl;

  Solution sol;

//  std::string s1 = "aabcc";
//  std::string s2 = "dbbca";
//  std::string s3 = "aadbbcbcac";
//  std::string s3 = "aadbbbaccc";

  std::string s1 = "";
  std::string s2 = "b";
  std::string s3 = "b";

  std::cout << "Input:\n";
  Output(s1);
  Output(s2);
  Output(s3);

  std::cout << "Output:\n";
  Output(sol.isInterleave(s1, s2, s3));

  return 0;
}<commit_msg>Fix a bug in InterleavingString.cpp<commit_after>/*
 * Copyright (c) 2013 <NAME>.
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * @author	<NAME> <<EMAIL>>
 * @date		2013-1-8
 */

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

class Solution {
public:
  bool isInterleave(string s1, string s2, string s3) {
      int n1 = s1.size();
      int n2 = s2.size();
      int n3 = s3.size();
      if (n1 + n2 != n3) return false;
      vector<vector<bool> > d(n1 + 1, vector<bool>(n2 + 1, false));
      d[0][0] = true;
      for (int i = 0; i < n3; ++i) {
          for (int j = std::max(0, i - n2); j <= i && j <= n1; ++j) {
            if (d[j][i - j]) {
              if (j < n1 && s1[j] == s3[i]) {
                d[j + 1][i - j] = true;
              }
              if (i - j < n2 && s2[i - j] == s3[i]) {
                d[j][i - j + 1] = true;
              }
            }
          }
      }
      return d[n1][n2];
  }
};

#include "util.h"

void Solve(const std::string& s1, const std::string& s2, const std::string& s3) {
  Solution sol;

  Output("Input:");
  Output(s1);
  Output(s2);
  Output(s3);

  Output("Output:");
  Output(sol.isInterleave(s1, s2, s3));

}

int main(int argc, char **argv) {
  std::cout << "------" << argv[0] << "------" << std::endl;


//  std::string s1 = "aabcc";
//  std::string s2 = "dbbca";
//  std::string s3 = "aadbbcbcac";
//  std::string s3 = "aadbbbaccc";

//  std::string s1 = "";
//  std::string s2 = "b";
//  std::string s3 = "b";

  std::string s1 = "aabd";
  std::string s2 = "abdc";
  std::string s3 = "aabdbadc";

  Solve("", "", "");
  Solve("cbcccbabbccbbcccbbbcabbbabcababbbbbbaccaccbabbaacbaabbbc",
      "abcbbcaababccacbaaaccbabaabbaaabcbababbcccbbabbbcbbb",
      "abcbcccbacbbbbccbcbcacacbbbbacabbbabbcacbcaabcbaaacbcbbbabbbaacacbbaaaabccbcbaabbbaaabbcccbcbabababbbcbbbcbb");

  return 0;
}
{'fraction_non_alphanumeric': 0.15749796251018744, 'fraction_numerical': 0.026487367563162185, 'mean_word_length': 2.511444921316166, 'pattern_counts': {'":': 0, '<': 54, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4651437', 'n_tokens_mistral': 1787, 'n_tokens_neox': 1732, 'n_words': 537}