Comment trouver la plus longue palindrome dans une chaîne? [dupliquer]
https://stackoverflow.com/questions/2677000
-
28-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Cette question a déjà une réponse ici:
Possible en double: écrire une fonction qui renvoie le plus long palindrome dans une chaîne
Je sais comment faire en O (n ^ 2). Mais il semble qu'il existe une meilleure solution.
Je l'ai trouvé cette , et il y a un lien vers O (n) réponse, mais il est écrit en Haskell et pas clair pour moi.
Il serait bien d'obtenir une réponse en c # ou similaire.
La solution
Je l'ai trouvé d'explication claire de la solution ici . Merci à Justin pour ce lien.
Vous pouvez y trouver des implémentations Python et Java de l'algorithme (la mise en œuvre de C contient des erreurs).
Et voici C # mise en œuvre de qui est juste une traduction de ces algorithmes.
public static int LongestPalindrome(string seq)
{
int Longest = 0;
List<int> l = new List<int>();
int i = 0;
int palLen = 0;
int s = 0;
int e = 0;
while (i<seq.Length)
{
if (i > palLen && seq[i-palLen-1] == seq[i])
{
palLen += 2;
i += 1;
continue;
}
l.Add(palLen);
Longest = Math.Max(Longest, palLen);
s = l.Count - 2;
e = s - palLen;
bool found = false;
for (int j = s; j > e; j--)
{
int d = j - e - 1;
if (l[j] == d)
{
palLen = d;
found = true;
break;
}
l.Add(Math.Min(d, l[j]));
}
if (!found)
{
palLen = 1;
i += 1;
}
}
l.Add(palLen);
Longest = Math.Max(Longest, palLen);
return Longest;
}
Autres conseils
Et voici sa version java:
public static int LongestPalindrome(String seq) {
int Longest = 0;
List<Integer> l = new ArrayList<Integer>();
int i = 0;
int palLen = 0;
int s = 0;
int e = 0;
while (i < seq.length()) {
if (i > palLen && seq.charAt(i - palLen - 1) == seq.charAt(i)) {
palLen += 2;
i += 1;
continue;
}
l.add(palLen);
Longest = Math.max(Longest, palLen);
s = l.size() - 2;
e = s - palLen;
boolean found = false;
for (int j = s; j > e; j--) {
int d = j - e - 1;
if (l.get(j) == d) {
palLen = d;
found = true;
break;
}
l.add(Math.min(d, l.get(j)));
}
if (!found) {
palLen = 1;
i += 1;
}
}
l.add(palLen);
Longest = Math.max(Longest, palLen);
return Longest;
}
Récemment, j'écrit le code suivant lors de l'entrevue ...
public string FindMaxLengthPalindrome(string s)
{
string maxLengthPalindrome = "";
if (s == null) return s;
int len = s.Length;
for(int i = 0; i < len; i++)
{
for (int j = 0; j < len - i; j++)
{
bool found = true;
for (int k = j; k < (len - j) / 2; k++)
{
if (s[k] != s[len - (k - j + 1)])
{
found = false;
break;
}
}
if (found)
{
if (len - j > maxLengthPalindrome.Length)
maxLengthPalindrome = s.Substring(j, len - j);
}
if(maxLengthPalindrome.Length >= (len - (i + j)))
break;
}
if (maxLengthPalindrome.Length >= (len - i))
break;
}
return maxLengthPalindrome;
}
Je suis arrivé à cette question quand je pris une interview.
J'ai découvert quand j'étais retour à la maison, malheureusement.
public static string GetMaxPalindromeString(string testingString)
{
int stringLength = testingString.Length;
int maxPalindromeStringLength = 0;
int maxPalindromeStringStartIndex = 0;
for (int i = 0; i < testingString.Length; i++)
{
int currentCharIndex = i;
for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
{
bool isPalindrome = true;
if (testingString[currentCharIndex] != testingString[lastCharIndex])
{
continue;
}
for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < lastCharIndex / 2; nextCharIndex++)
{
if (testingString[nextCharIndex] != testingString[lastCharIndex - 1])
{
isPalindrome = false;
break;
}
}
if (isPalindrome)
{
if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
{
maxPalindromeStringStartIndex = currentCharIndex;
maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
}
}
break;
}
}
return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
}
public static string GetMaxPalindromeString(string testingString)
{
int stringLength = testingString.Length;
int maxPalindromeStringLength = 0;
int maxPalindromeStringStartIndex = 0;
for (int i = 0; i < stringLength; i++)
{
int currentCharIndex = i;
for (int lastCharIndex = stringLength - 1; lastCharIndex > currentCharIndex; lastCharIndex--)
{
if (lastCharIndex - currentCharIndex + 1 < maxPalindromeStringLength)
{
break;
}
bool isPalindrome = true;
if (testingString[currentCharIndex] != testingString[lastCharIndex])
{
continue;
}
else
{
int matchedCharIndexFromEnd = lastCharIndex - 1;
for (int nextCharIndex = currentCharIndex + 1; nextCharIndex < matchedCharIndexFromEnd; nextCharIndex++)
{
if (testingString[nextCharIndex] != testingString[matchedCharIndexFromEnd])
{
isPalindrome = false;
break;
}
matchedCharIndexFromEnd--;
}
}
if (isPalindrome)
{
if (lastCharIndex + 1 - currentCharIndex > maxPalindromeStringLength)
{
maxPalindromeStringStartIndex = currentCharIndex;
maxPalindromeStringLength = lastCharIndex + 1 - currentCharIndex;
}
break;
}
}
}
if(maxPalindromeStringLength>0)
{
return testingString.Substring(maxPalindromeStringStartIndex, maxPalindromeStringLength);
}
return null;
}
C #
D'abord, je cherche même palindromes de longueur. Ensuite, je recherche palindromes de longueur impair. Quand il trouve un palindrome, on détermine la longueur et définit la longueur maximale en conséquence. La complexité des cas en moyenne pour cela est linéaire.
protected static int LongestPalindrome(string str)
{
int i = 0;
int j = 1;
int oldJ = 1;
int intMax = 1;
int intCount = 0;
if (str.Length == 0) return 0;
if (str.Length == 1) return 1;
int[] intDistance = new int[2] {0,1};
for( int k = 0; k < intDistance.Length; k++ ){
j = 1 + intDistance[k];
oldJ = j;
intCount = 0;
i = 0;
while (j < str.Length)
{
if (str[i].Equals(str[j]))
{
oldJ = j;
intCount = 2 + intDistance[k];
i--;
j++;
while (i >= 0 && j < str.Length)
{
if (str[i].Equals(str[j]))
{
intCount += 2;
i--;
j++;
continue;
}
else
{
break;
}
}
intMax = getMax(intMax, intCount);
j = oldJ + 1;
i = j - 1 - intDistance[k];
}
else
{
i++;
j++;
}
}
}
return intMax;
}
protected static int getMax(int a, int b)
{
if (a > b) return a; return b;
}
