Line data    Source code

       1              : // Copyright (c) 2023 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2023/11/30 23:09
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <string>
      21              : #include <vector>
      22              : 
      23              : namespace {
      24              : class Solution {
      25              : public:
      26            3 :     int longestCommonSubsequence(const std::string& text1, const std::string& text2) {
      27            3 :         int len1 = text1.length();
      28            3 :         int len2 = text2.length();
      29            3 :         std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1, 0));
      30            3 :         int ret = 0;
      31           14 :         for (int i = 1; i <= len1; ++i) {
      32           44 :             for (int j = 1; j <= len2; ++j) {
      33           33 :                 if (text1[i - 1] == text2[j - 1]) {
      34            6 :                     dp[i][j] = dp[i - 1][j - 1] + 1;
      35              :                 } else {
      36           27 :                     dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      37              :                 }
      38           33 :                 if (dp[i][j] > ret) {
      39            6 :                     ret = dp[i][j];
      40              :                 }
      41              :             }
      42              :         }
      43            3 :         return ret;
      44            3 :     }
      45              : };
      46              : } // namespace
      47              : 
      48            4 : TEST(Leetcode, longest_common_subsequence) {
      49            1 :     Solution s;
      50            1 :     EXPECT_EQ(3, s.longestCommonSubsequence("abcde", "ace"));
      51            1 :     EXPECT_EQ(3, s.longestCommonSubsequence("abc", "abc"));
      52            1 :     EXPECT_EQ(0, s.longestCommonSubsequence("abc", "def"));
      53            1 : }