class Solution { public: bool isSubsequence(string s, string t) { bool res; res = ifExist(s, t); return res; } private: bool ifExist(string& substring, string& subt){ int n = substring.size(); int m = subt.size(); if(n >= m || substring != subt) return false; if(m == 0 && n != 0) return true; if(m != 0 && n == 0) return false; for(int i = 0; i < n; i++){ if(subt[i] == substring[0]){ subt = subt.substr(0, i+1); substring = substring.substr(1,n); ifExist(substring, subt); } } return true; } };

这段代码是一个判断字符串s是否为字符串t的子序列的函数。函数首先调用私有函数ifExist来实现判断。私有函数ifExist的实现过程是，首先判断s是否等于t或s的长度是否大于等于t的长度，如果是则返回false；接着判断如果t为空字符串但s非空，则返回true；如果s为空字符串但t非空，则返回false。最后使用一个for循环来遍历t字符串的每个字符，如果找到了与s的第一个字符相同的字符，则对t和s分别进行截取操作，将对应的字符去掉并递归调用ifExist函数，直到s为空字符串为止。最后返回true。

相关问题

请将下面代码转为 java：class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: import functools @functools.lru_cache(None) def back_track(s): if(not s): return True res=False for i in range(1,len(s)+1): if(s[:i] in wordDict): res=back_track(s[i:]) or res return res return back_track(s)

以下是代码转化为 Java 的版本：

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Map<String, Boolean> cache = new HashMap<>();
        return backTrack(s, wordDict, cache);
    }

    private boolean backTrack(String s, List<String> wordDict, Map<String, Boolean> cache) {
        if ("".equals(s)) {
            return true;
        }

        if (cache.containsKey(s)) {
            return cache.get(s);
        }

        boolean res = false;
        for (int i = 1; i <= s.length(); i++) {
            if (wordDict.contains(s.substring(0, i))) {
                res = backTrack(s.substring(i), wordDict, cache) || res;
            }
        }

        cache.put(s, res);
        return res;
    }
}

给你一个字符串 s，找到 s 中最长的回文子串。

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。

回文串是指正着读和反着读都一样的字符串。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

解题思路：

1.暴力法

暴力法是最简单直接的方法，遍历所有子串，判断是否为回文串，记录最长的回文串。

时间复杂度：O(n^3)

2.中心扩展法

中心扩展法是基于回文串的对称性质，从中心向两边扩展，判断是否为回文串，记录最长的回文串。

时间复杂度：O(n^2)

3.动态规划法

动态规划法是基于回文串的子串也是回文串的性质，利用状态转移方程，记录最长的回文串。

时间复杂度：O(n^2)

4.马拉车算法

马拉车算法是基于回文串的对称性质和回文串的最大半径，利用中心扩展法的思想，减少重复计算，记录最长的回文串。

时间复杂度：O(n)

参考代码：

1.暴力法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string res = "";
for (int i = ; i < n; i++) {
for (int j = i; j < n; j++) {
int len = j - i + 1;
if (len > res.size() && isPalindrome(s, i, j)) {
res = s.substr(i, len);
}
}
}
return res;
}
bool isPalindrome(string s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
};

2.中心扩展法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string res = "";
for (int i = ; i < n; i++) {
string s1 = palindrome(s, i, i);
string s2 = palindrome(s, i, i + 1);
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
string palindrome(string s, int left, int right) {
while (left >= && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
};

3.动态规划法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = , maxLen = 1;
for (int i = ; i < n; i++) {
dp[i][i] = true;
}
for (int j = 1; j < n; j++) {
for (int i = ; i < j; i++) {
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
return s.substr(start, maxLen);
}
};

4.马拉车算法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string t = "#";
for (int i = ; i < n; i++) {
t += s[i];
t += "#";
}
n = t.size();
vector<int> p(n, );
int center = , maxRight = , start = , maxLen = 1;
for (int i = ; i < n; i++) {
if (i < maxRight) {
int mirror = 2 * center - i;
p[i] = min(maxRight - i, p[mirror]);
}
int left = i - (p[i] + 1), right = i + (p[i] + 1);
while (left >= && right < n && t[left] == t[right]) {
p[i]++;
left--;
right++;
}
if (i + p[i] > maxRight) {
center = i;
maxRight = i + p[i];
}
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substr(start, maxLen);
}
};