时间复杂度O(NM|s|)，空间复杂度O(N)「C++ 代码」 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param dic string字符串vector * @return bool布尔型 */ bool wordDiv(stri...

时间复杂度O(N), 空间复杂度O(1)。贪心思想：从左往右遍历，将所有的星号视作左括号，若此时左括号的数目仍然小于右括号，那么一定不成立。相似地再从右往左遍历一遍。最后若不为False, 则说明星号可以自适应转化得到True.[C++ 代码] class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ bool isValidString(stri...

时间复杂度O(N), 空间复杂度O(N)。可以发现，状态转移方程中，dp[i]仅与dp[i-1]有关，所以我们可以利用滚动数组的思想进行简化达到O(1)的空间复杂度。「C++ 代码」 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> FindGreatestSumOfSubArray(...

判断字符串的子序列问题，一种做法是基于动态规划计算公共子序列，若公共子序列等于字符串S则说明S是T的子序列。这样做的解法时间复杂度是O(n2），但实际上不用这么麻烦，存在更简单容易理解的时间复杂度为O(N)的方法：【C++ 代码】 class Solution { public: /** * * * * @param S string字符串 * @param T string字符串 * @return bool布尔型 */ bool isSubsequence(string S, string T) ...

class Solution { vector<int> direction = {-1, 0, 1, 0, -1}; int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>>& dp){ // 如果不为零，说明在之前的递归中已经计算过以（x, y）为起点的最长路径，此时直接返回即可 if(dp[x][y]!=0) return dp[x][y]; // 1. 如果为零，首先赋值自身为1 dp...

最长回文子串（注：非子序列），考虑使用中心扩展法，时间复杂度O(n²)，空间复杂度O(1)。 int expand(string& A, int left, int right){ int n = A.length(); // 考虑边界处理 while(left>=0 && right<n && A[left]==A[right]){ --left; ++right; } return right-left-1; } int get...