给定一个字符串,我必须从中找出满足以下条件的子字符串
子字符串中的所有字符都相同。例如:aa、bbb、cccc。
除中间字符外的所有字符都必须相同。 例如:aba、bbabb等
我做了一个类似这样的算法
我使用两个循环来读取字符串,第一个循环保存第一个字符,第二个循环遍历字符串。
然后我将子字符串发送到 vet() 以查看子字符串是否包含小于或等于两个字符。 如果子字符串包含两个字符,那么我检查它是否是回文
public static int reverse(String s)
{
String wrd="";
for(int i = s.length()-1 ;i>=0;i--)
wrd = wrd + s.charAt(i);
if(s.equals(wrd))
return 1;
else
return 0;
}
public static boolean vet(String s)
{
HashSet<Character> hs = new HashSet<>();
for(char c : s.toCharArray())
{
hs.add(c);
}
if(hs.size() <= 2)
return true;
else
return false;
}
static long substrCount(int n, String s) {
List<String> al = new ArrayList<>();
for(int i=0;i<s.length();i++)
{
for(int j=i;j<s.length();j++)
{
if(vet(s.substring(i,j+1)))
{
if(reverse(s.substring(i,j+1)) == 1)
al.add(s.substring(i,j+1));
}
}
}
return al.size();
}
此代码对于小字符串工作正常,但是如果字符串很大(例如一万个字符),此代码将抛出时间限制异常。
我怀疑破坏字符串并在 substrCount() 中创建子字符串的循环导致了时间复杂度,因为它具有嵌套循环。
请检查此代码并提供更好的方法来破坏字符串,或者如果由于其他部分而导致复杂性增加,请告诉我。
最佳答案
- 您可以将字符串左侧和右侧的计数收集到 2 个单独的数组中。
- 现在,我们以以下方式收集计数:如果前一个字符等于当前字符,则将计数增加 1,否则将其设置为 1。
示例:
a a b a a c a a
1 2 1 1 2 1 1 2 // left to right
2 1 1 2 1 1 2 1 // right to left
对于所有字符都相等的字符串,我们只是在迭代自身时收集所有字符。
对于除了中间字符之外全部相等的字符串,可以使用上面的表格,可以收集如下字符串:
伪代码:
if(str.charAt(i-1) == str.charAt(i+1)){ // you will add checks for boundaries
int min_count = Math.min(left[i-1],right[i+1]);
for(int j=min_count;j>=1;--j){
set.add(str.substring(i-j,i+j+1));
}
}
更新:
以下是我接受的解决方案。
static long substrCount(int n, String s) {
long cnt = 0;
int[] left = new int[n];
int[] right = new int[n];
int len = s.length();
for(int i=0;i<len;++i){
left[i] = 1;
if(i > 0 && s.charAt(i) == s.charAt(i-1)) left[i] += left[i-1];
}
for(int i=len-1;i>=0;--i){
right[i] = 1;
if(i < len-1 && s.charAt(i) == s.charAt(i+1)) right[i] += right[i+1];
}
for(int i=len-1;i>=0;--i){
if(i == 0 || i == len-1) cnt += right[i];
else{
if(s.charAt(i-1) == s.charAt(i+1) && s.charAt(i-1) != s.charAt(i)){
cnt += Math.min(left[i-1],right[i+1]) + 1;
}else if(s.charAt(i) == s.charAt(i+1)) cnt += right[i];
else cnt++;
}
}
return cnt;
}
算法:
- 该算法与上面解释的相同,但有一些额外的内容。
- 如果字符位于边界,请输入
0
或在len-1
,我们只看right[i]
计算字符串,因为我们没有left
在这里。 如果字符在此边界内,我们将进行如下检查:
- 如果前一个字符等于下一个字符,我们检查前一个字符是否不等于当前字符。我们这样做是因为,我们希望避免将来在当前迭代本身添加字符串(例如像
aaaaa
这样的字符串,我们位于中间a
)。 - 第二个条件是
s.charAt(i) == s.charAt(i+1)
,意思是,我们再次有像aaa
这样的字符串我们是第一个a
。所以我们只需添加right[i]
指示添加类似a
的字符串,aa
,aaa
)。 - 第三个是
cnt++
意思是添加个性。
- 如果前一个字符等于下一个字符,我们检查前一个字符是否不等于当前字符。我们这样做是因为,我们希望避免将来在当前迭代本身添加字符串(例如像
您可以进行一些优化,例如完全避免
right
数组等,但我把它留给你作为练习。时间复杂度:O(n),空间复杂度:O(n)
关于java - 使用循环创建子字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60054222/