logo标签列表

检查是否可以得到回文字符串

c++algorithm
6

给定一个字符串S，我们需要判断是否可以通过删除其中一项来使它成为回文。我采用了修改编辑距离方法的O（N ^ 2）方法。是否有更好的方法呢？

我的方法：

int ModifiedEditDistance(const string& a, const string& b, int k) {
    int i, j, n = a.size();
    int dp[MAX][MAX];
    memset(dp, 0x3f, sizeof dp);    
    for (i = 0 ; i < n; i++)
        dp[i][0] = dp[0][i] = i;

    for (i = 1; i <= n; i++) {
        int from = max(1, i-k), to = min(i+k, n);
        for (j = from; j <= to; j++) {
            if (a[i-1] == b[j-1])           // same character
                dp[i][j] = dp[i-1][j-1];    
            // note that we don't allow letter substitutions

            dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]); // delete character j
            dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); // insert character i
        }
    }
    return dp[n][n];
}

如何改善空间复杂度，因为字符串的最大大小可以达到10^5。

请帮忙。

例子：如果字符串是abc，则答案是“NO”，如果字符串是“abbcbba”，则答案是“YES”。

2
"abbcbba"已经是一个回文，不需要删除任何字符。 - John Zwinck
@JohnZwinck 但我们需要恰好删除一个字符。然后告诉答案。因此，删除“c”仍将使其成为回文。 - android maniac
2
@JohnZwinck 我认为他的意思是你可以去掉 'c'，它仍然是一个回文。 - Barry
1
这是来自在线编程评测系统的问题吗？哪一个？ - vz0
2
想一想，你会如何在纸上解决这个问题？你可能会用手指从单词的两端向中间移动，检查是否有差异。 - Colonel Panic
显示剩余6条评论
9个回答
9
关键观察点是如果第一个和最后一个字符相同，则无需删除它们中的任何一个。也就是说，只有当 STRING 至少为一个字符长时，才能通过删除一个字母来将 xSTRINGx 变成回文字符串。
你希望定义一个方法（请原谅使用 Java 语法 - 我不是 C++ 程序员）:
boolean canMakePalindrome(String s, int startIndex, int endIndex, int toRemove);

该函数用于确定从startIndex到endIndex-1的字符串部分是否可以通过删除toRemove个字符变成回文字符串。

当考虑canMakePalindrome(s, i, j, r)时，可以将其定义为以下更小的问题：

  1. 如果j-i等于1，则返回true；如果它等于0，则当且仅当r等于0时返回true。这里的要点是一个1个字符的字符串是回文的，无论你删除哪个字符；长度为0的字符串也是回文的，但无法通过删除字符来制作它（因为没有任何字符可供删除）。
  2. 如果s[i]和s[j-1]相同，则与canMakePalindrome(s, i+1, j-1, r)具有相同的答案。
  3. 如果它们不同，则需要删除s[i]或s[j-1]中的一个字符。如果toRemove为零，则返回false，因为您没有剩余的字符可供删除。如果toRemove等于1，则在canMakePalindrome(s, i+1, j, 0)或canMakePalindrome(s, i, j-1, 0)中仅需返回true即可。这是因为现在您正在测试如果删除这两个字符中的一个，它是否已经是回文字符串。

现在这可以很容易地编码出来。

如果您想允许删除多个字符，则可以使用相同的思想，但要使用动态规划。对于只需要删除一个字符的情况，动态规划将减少常数因子，但不会减少渐近时间复杂度（与字符串长度成线性比）。

这个解决方案的时间复杂度是多少？ - kraskevich
@chiastic-security，你能提供一些伪代码吗？ - android maniac
1
@user2040251 我认为它是线性的（因为你只能删除一个字符）。 - chiastic-security
@j_random_hacker 你是不是想把那个发到另一个答案里？ - chiastic-security
1
@androidmaniac 在堆上是O(1)，运行时间为O(n)。需要注意的是，如果您使用递归按原样实现它，它在堆栈上将是O(n)，很可能导致堆栈溢出。然而，将算法描述为递归是一件非常普遍的事情，您只需要足够聪明地将其编写为for循环即可。以上与我的答案或JohnWincks的答案相同。 - IdeaHat
显示剩余5条评论
4

伪代码（类似于这个，我没有测试过它）。

它基于检测可以删除字符的条件，即

  1. 只有一个错误字符
  2. 它是回文（0个不匹配）

时间复杂度为O(n)，空间复杂度为O(1)。

 bool foo(const std::string& s)
 {
   int i = 0;
   int j = s.size()-1;
   int mismatch_count = 0;
   while (i < j)
   {
       if (s[i]==s[j])
       {
          i++; j--;
       }
       else
       {
          mismatch_count++;
          if (mismatch_count > 1) break;
          //override first preference if cannot find match for next character
          if (s[i+1] == s[j] && ((i+2 >= j-1)||s[i+2]==s[j-1]))
          {
             i++;
          }
          else if (s[j-1]==s[i])
          {
             j--;
          }
          else
          {
             mismatch_count++; break;
          }
       }
    }  
    //can only be a palendrome if you remove a character if there is exactly one mismatch
    //or if a palendrome
    return (mismatch_count == 1) || (mismatch_count == 0);
 }
你的代码似乎有问题，因为它为aaa和abba提供了0。 - android maniac
返回1给我吗？这两个都是回文，所以mismatch_count==0。 - IdeaHat
但我们仍然可以删除一个字符，它们仍然是回文。因此答案应该是1而不是0。 - android maniac
@androidmaniac return (mismatch_count == 1) || (mismatch_count == 0); 这段代码是用来检查这个的吗？ - IdeaHat
@MadScienceDreams 字符串太长了，无法在此处粘贴。但是当我运行您的解决方案与JohnZwinck的解决方案时，两者得出的答案不同。而他的解决方案是正确的。 - android maniac
显示剩余3条评论
2
这里有一个（稍微不完整的）解决方案，它需要O(n)时间和O(1)空间。
// returns index to remove to make a palindrome; string::npos if not possible
size_t willYouBeMyPal(const string& str)
{
  size_t toRemove = string::npos;
  size_t len = str.length();

  for (size_t c1 = 0, c2 = len - 1; c1 < c2; ++c1, --c2) {
    if (str[c1] != str[c2]) {
      if (toRemove != string::npos) {
        return string::npos;
      }

      bool canRemove1 = str[c1 + 1] == str[c2];
      bool canRemove2 = str[c1] == str[c2 - 1];
      if (canRemove1 && canRemove2) {
        abort(); // TODO: handle the case where both conditions are true
      } else if (canRemove1) {
        toRemove = c1++;
      } else if (canRemove2) {
        toRemove = c2--;
      } else {
        return string::npos;
      }
    }
  }

  // if str is a palindrome already, remove the middle char and it still is
  if (toRemove == string::npos) {
    toRemove = len / 2;
  }

  return toRemove;
}

留给读者的练习是如果您遇到以下情况应该怎么办：
abxyxcxyba

正确的解决方案是：
ab_yxcxyba

但是你可能会走上一条错误的道路：

abxyxcx_ba

因此，当您发现两侧的“下一个”字符都是可能的解决方案时，您需要评估这两种可能性。

@androidmaniac：你说得对，我通过简化结尾处的条件来修复了已经是回文的情况。 - John Zwinck
它为abdbca提供了npos。 - android maniac
@androidmaniac：再次正确，我刚刚发现了那个错误并与你一起修复了它。 :) 我需要c2--而不是c2++。 现在对于abdbca它会给出4，这使得abdba。 - John Zwinck
@JohnZwinck 发现了多条路径，干得好。希望你不介意，我把它用在我的答案里了 :-P - IdeaHat
2

我写了一个时间复杂度为O(n)的示例，对我进行的测试都有效。虽然测试不是很多 :D 其背后的想法是忽略第一个和最后一个字母（如果它们相同），如果它们不同，则删除其中一个，并推理出字符串足够小时会发生什么。使用循环而不是递归也可以得到相同的结果，这将节省一些空间（使其为O(1)），但在我看来更难理解且容易出错。

bool palindrome_by_1(const string& word, int start, int end, bool removed = false)  // Start includes, end excludes
{
    if (end - start == 2){
        if (!removed)
            return true;

        return word[start] == word[end - 1];
    }

    if (end - start == 1)
        return true;


    if (word[start] == word[end - 1])
        return palindrome_by_1(word, start + 1, end - 1, removed);

    // After this point we need to remove a letter
    if (removed) 
        return false;

    // When two letters don't match, try to eliminate one of them
    return palindrome_by_1(word, start + 1, end, true) || palindrome_by_1(word, start, end - 1, true);

}
@chiastic-security 写了一个回答，使用了和我相同的概念。这不是我的意图 xD。 - SlySherZ
1

检查单个字符串是否是回文的时间复杂度为O(n)。您可以实现类似的算法，移动两个指针，一个从开头，另一个从结尾开始。只要字符相同，就移动每个指针，当第一次不匹配时，尝试匹配可以跳过的字符，并且在其余字符相同时保持移动两个指针。跟踪第一次不匹配。这是O(n)。

1
我希望我的算法能够通过而不需要提供代码。
如果一个单词a1a2....an 可以通过删除ak变成回文，我们可以按照以下方式搜索k：
如果a1 != an，那么唯一可能的k是1或n。只需检查a1a2....an-1或a2a3....an是否为回文。
如果a1 == an，则下一步是解决a2....an-1的相同问题。因此我们在这里有一个递归。
我认为我的想法与chiastic-security提供的类似。 - Timothy Ha
0

公共静态布尔型pal（String s，int start，int end）{

    if(end-start==1||end==start)
        return true;

    if(s.charAt(start)==s.charAt(end))
        return pal(s.substring(start+1, end),0,end-2);

    else{

        StringBuilder sb=new StringBuilder(s);
        sb.deleteCharAt(start);
        String x=new String(sb);
        if(x.equals(sb.reverse().toString()))
            return true;

        StringBuilder sb2=new StringBuilder(s);
        sb2.deleteCharAt(end);
        String x2=new String(sb2);
        if(x2.equals(sb2.reverse().toString()))
            return true;


    }

    return false;

}
0
我尝试过下面的方法，f和b是不匹配字符的索引。
int canwemakepal(char *str)//str input string
{
    long int f,b,len,i,j;
   int retval=0;
   len=strlen(str);
    f=0;b=len-1;
    while(str[f]==str[b] && f<b)//continue matching till we dont get a mismatch
    {
        f++;b--;
    }
    if(f>=b)//if the index variable cross over each other, str is palindrome,answer is yes
    {
        retval=1;//true
    }
    else if(str[f+1]==str[b])//we get a mismatch,so check if removing character at str[f] will give us a palindrome
    {
        i=f+2;j=b-1;
        while(str[i]==str[j] && i<j)
        {
            i++;j--;
        }
        if(i>=j)
        retval=1;
        else
        retval=0;
    }
    else if(str[f]==str[b-1])//else check the same for str[b]
    {
        i=f+1;j=b-2;
        while(str[i]==str[j] && i<j)
        {
            i++;j--;
        }
        if(i>=j)
        retval=1;
        else
        retval=0;
    }
    else 
    retval=0;

    return retval;

}
0
I created this solution,i tried with various input giving correct result,still not accepted as correct solution,Check it n let me know if m doing anything wrong!! Thanks in advance.
public static void main(String[] args) 
{

    Scanner s = new Scanner(System.in);
    int t = s.nextInt();
    String result[] = new String[t];
    short i = 0;
    while(i < t)
    {
        String str1 = s.next();
        int length  = str1.length();
        String str2 = reverseString(str1);
        if(str1.equals(str2))
        {
                result[i] = "Yes";
        }
        else 
        {
                if(length == 2)
                {
                    result[i] = "Yes";
                }
                else
                {
                    int x = 0,y = length-1;

                    int counter = 0;
                    while(x<y)
                    {
                        if(str1.charAt(x) == str1.charAt(y))
                        {
                            x++;
                            y--;
                        }
                        else
                        {
                            counter ++;
                            if(str1.charAt(x) == str1.charAt(y-1))
                            {
                                y--;
                            }
                            else if(str1.charAt(x+1) == str1.charAt(y))
                            {
                                x++;
                            }
                            else
                            {
                                counter ++;
                                break;
                            }
                        }

                    }
                    if(counter >= 2)
                    {
                        result[i] = "No";
                    }
                    else
                        result[i]="Yes";
                }

        }
        i++;

    } // Loop over

    for(int j=0; j<i;j++)
    {
        System.out.println(result[j]);
    }
}

public static String reverseString(String original)
{
    int length = original.length();
    String reverse = "";
     for ( int i = length - 1 ; i >= 0 ; i-- )
         reverse = reverse + original.charAt(i);
    return reverse;  
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接