leetcode-5-最长回文子串 题型:动态规划 难度:中等 题目:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 代码:
class Solution {
public:
string
longestPalindrome(string s
) {
int nlen
= s
.size();
vector
<vector
<int> > dp(nlen
,vector
<int>(nlen
,0));
string res
= "";
for(int i
=1;i
<=nlen
;i
++)
{
for(int left
=0;i
+left
-1<nlen
;left
++)
{
int right
= left
+i
-1;
if(i
== 1)
{
dp
[left
][right
] = 1;
}
else if(i
== 2)
{
dp
[left
][right
] = (s
[left
]==s
[right
]);
}
else
{
if(s
[left
] == s
[right
] && dp
[left
+1][right
-1]==1)
dp
[left
][right
] = 1;
}
if(dp
[left
][right
]==1 && i
>res
.size() )
{
res
= s
.substr(left
,i
);
}
}
}
return res
;
}
};
leetcode-984-不含AAA或BBB的字符串 题型:字符串 难度:中等 题目:给定两个整数 A 和 B,返回任意字符串 S,要求满足:S 的长度为 A + B,且正好包含 A 个 ‘a’ 字母与 B 个 ‘b’ 字母; 子串 ‘aaa’ 没有出现在 S 中; 子串 ‘bbb’ 没有出现在 S 中。
class Solution {
public:
string
strWithout3a3b(int A
, int B
) {
string res
= "";
char a
,b
;
if(A
>= B
)
{
a
= 'a';
b
= 'b';
}
else
{
A
= A
^B
;
B
= A
^B
;
A
= A
^B
;
a
= 'b';
b
= 'a';
}
while(A
|| B
)
{
if(A
)
{
res
+= a
;
A
--;
}
if(A
> B
)
{
res
+= a
;
A
--;
}
if(B
)
{
res
+= b
;
B
--;
}
}
return res
;
}
};
leetcode-44-通配符匹配 题型:动态规划 难度:困难 题目:给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘’ 的通配符匹配。’?’ 可以匹配任何单个字符。’’ 可以匹配任意字符串(包括空字符串)。两个字符串完全匹配才算匹配成功。 说明:s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。 代码:
class Solution {
public:
bool isMatch(string s
, string p
) {
int len1
= s
.size();
int len2
= p
.size();
vector
<vector
<int> > dp(len1
+1,vector
<int>(len2
+1,false));
dp
[0][0] = true;
for(int i
=0;i
<len2
;i
++)
{
if(p
[i
] == '*')
dp
[0][i
+1] = true;
else
break;
}
for(int i
=1;i
<=len1
;i
++)
{
for(int j
=1;j
<=len2
;j
++)
{
if(s
[i
-1] == p
[j
-1])
{
dp
[i
][j
] = dp
[i
-1][j
-1];
}
else if(p
[j
-1] == '?')
{
dp
[i
][j
] = dp
[i
-1][j
-1];
}
else if(p
[j
-1] == '*')
{
dp
[i
][j
] =( dp
[i
-1][j
]||dp
[i
][j
-1]);
}
}
}
return dp
[len1
][len2
];
}
};