标签: palindrome

例如字符串"abaccddccefe"中的"ccddcc"

我想到了一个解决方案,但它在O(n ^ 2)时间运行

Algo 1:

步骤:它是一种强力方法

1. 对于j = i + 1到j小于array.length,
   对于i = 1到i小于array.length -1
   , 有2个for循环
2. 这样,您可以从数组中获取每个可能组合的子字符串
3. 有一个回文功能,检查字符串是否是回文
4. 所以对于每个子串(i,j)调用这个函数,如果它是一个回文存储它在一个字符串变量中
5. 如果您找到下一个回文子串并且如果它大于当前回归,则将其替换为当前的回归.
6. 最后你的字符串变量将有答案

问题:1.这个算法在O(n ^ 2)时间运行.

算法2:

1. 反转字符串并将其存储在不同的数组中
2. 现在找到两个数组之间最大的匹配子字符串
3. 但这也是在O(n ^ 2)时间内运行的

你们能想到一个在更好的时间里运行的算法吗？如果可能的话O(n)时间

这是一个我无法回答的面试问题:

如何使用正则表达式检查字符串是回文？

ps已经有一个问题" 如何检查给定的字符串是否是回文？ "它提供了很多不同语言的答案,但没有使用正则表达式的答案.

甲回文是单词,短语,数字或的单元的其它序列可以读取在任一方向的方式相同.

为了检查单词是否是回文,我得到单词的字符数组并比较字符.我测试了它似乎工作.但是我想知道它是否正确或是否有待改进的地方.

这是我的代码:

public class Aufg1 {
    public static void main(String[] args) {
        String wort = "reliefpfpfeiller";
        char[] warray = wort.toCharArray(); 
        System.out.println(istPalindrom(warray));       
    }

    public static boolean istPalindrom(char[] wort){
        boolean palindrom = false;
        if(wort.length%2 == 0){
            for(int i = 0; i < wort.length/2-1; i++){
                if(wort[i] != wort[wort.length-i-1]){
                    return false;
                }else{
                    palindrom = true;
                }
            }
        }else{
            for(int i = 0; i < (wort.length-1)/2-1; i++){
                if(wort[i] != wort[wort.length-i-1]){
                    return false;
                }else{
                    palindrom = true;
                }
            }
        }
        return palindrom;
    } …

在花了大约6-8个小时试图消化Manacher的算法之后,我准备好了.但在此之前,这是最后一次在黑暗中拍摄:有人可以解释一下吗？我不关心代码.我希望有人解释算法.

这里似乎是其他人在解释算法时似乎喜欢的地方:http: //www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

我理解你为什么要把字符串转换成'#ab#'到#a#b#b#a#之后我就输了.例如,前面提到的网站的作者说该算法的关键部分是:

                      if P[ i' ] ? R – i,
                      then P[ i ] ? P[ i' ]
                      else P[ i ] ? P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])

这似乎是错误的,因为他/她在一点上说当P [i'] = 7并且P [i]不小于或等于R-i时P [i]等于5.

如果你不熟悉这个算法,这里有一些更多的链接:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html(我试过这个,但是术语很糟糕,令人困惑.首先,有些东西没有定义.还有太多的变量.你需要一个清单来回忆一下变量是指哪些变量.)

另一个是:http://www.akalin.cx/longest-palindrome-linear-time(祝你好运)

该算法的基本要点是在线性时间内找到最长的回文.它可以在O(n ^ 2)中以最小到中等的努力量完成.这个算法应该非常"聪明"才能将其降低到O(n).

我试图在字符串中找到最长的回文.蛮力解决方案需要O(n ^ 3)时间.我读到有一个使用后缀树的线性时间算法.我熟悉后缀树,很舒服地建造它们.如何使用构建的后缀树找到最长的回文.

我正在尝试使用Python检查回文.我的代码非常for密集.

在我看来,从C到Python的最大错误是尝试使用Python实现C逻辑,这使得事情运行缓慢,并且它只是没有充分利用语言.

我在这个网站上看到了.搜索"C-style for",Python没有C风格的循环.可能会过时,但我将其解释为Python有自己的方法.

我试过四处寻找,我找不到最新的(Python 3)建议.如何在不使用for循环的情况下解决Python中的回文挑战？

我在课堂上用C语言完成了这个,但是我想在Python中以个人为基础.问题来自欧拉项目,顺便说一下,伟大的网站.

def isPalindrome(n):
    lst = [int(n) for n in str(n)]
    l=len(lst)
    if l==0 || l==1:
        return True
    elif len(lst)%2==0:
        for k in range (l)
        #####
    else:
        while (k<=((l-1)/2)):
            if (list[]):
                #####   

for i in range (999, 100, -1):
    for j in range (999,100, -1):
        if isPalindrome(i*j):
            print(i*j)
            break

我在这里遗漏了很多代码.五个哈希只是我自己的提醒.

具体问题:

1. 在C中,我会创建一个for循环,将索引0与索引max进行比较,然后使用max-1索引0 + 1,直到某事为止.如何在Python中做到最好？

2. 我的for循环(在范围(999,100,-1)中,这是用Python做错的方法吗？

3. 有没有人对我的职位有任何好的建议,好的网站或资源？我不是程序员,我不想成为一名程序员,我只想学习足够的东西,这样当我写完学士学位论文(电子工程)时,我不必同时学习适用的编程语言在项目中取得好成绩."如何从基本的C转到Python的伟大应用",那种事情.

4. 任何特定的代码都可以很好地解决这个问题,我需要学习好的算法.我正在设想3种情况.如果值为零或单个数字,如果它是奇数长度,如果它是偶数长度.我打算为循环写...

PS:问题是:找到两个3位整数的最高值乘积,它也是一个回文.

这是来自Algorithms book(Vazirani)的问题(6.7 ch6),与发现最长回文的经典问题略有不同.我怎么解决这个问题 ？

如果从左到右或从右到左读取它是相同的,则子序列是回文.例如,序列

A,C,G,T,G,T,C,A,A,A,A,T,C,G

Run Code Online (Sandbox Code Playgroud)

有许多回文子序列,包括A,C,G,C,A和A,A,A,A (另一方面,子序列 A,C,T不是回文).设计一个算法,该算法采用一个序列x[1 ...n]并返回(最长的)最长的回文子序列.它的运行时间应该是O(n^2)

目标:任何语言.最小的函数,它将返回一个字符串是一个回文.这是我的Python:

R=lambda s:all(a==b for a,b in zip(s,reversed(s)))

50个字符.

接受的答案将是当前最小的答案 - 当发现较小的答案时,这将会改变.请指定您的代码所在的语言.

我想知道如何在javascript中编写回文,我输入不同的单词和程序显示单词是否是回文.例如,中午是回文,而坏则不是回文.

先感谢您.

^{这是一系列教育正则表达式文章的第三部分.它遵循这个正则表达式如何找到三角形数字？(首先介绍嵌套引用)和如何将^ nb ^ n与Java正则表达式匹配？ (前瞻性"计数"机制进一步详述).这部分介绍了一种特定形式的嵌套断言,当与嵌套引用结合使用时,Java正则表达式可以匹配大多数人认为"不可能"的东西:回文!}

回文的语言是非常规的 ; 它实际上是无上下文的(对于给定的字母表).也就是说,现代正则表达式实现不仅仅识别常规语言,Perl/PCRE的递归模式和.NET的平衡组可以很容易地识别回文(参见:相关问题).

但是,Java的正则表达式引擎既不支持这些"高级"功能.然而"某人" ^(*wink*)成功编写了以下正则表达式,这似乎做得很好(参见ideone.com):

public class Palindrome {
    // asserts that the entirety of the string matches the given pattern
    static String assertEntirety(String pattern) {
        return "(?<=(?=^pattern$).*)".replace("pattern", pattern);
    }

    public static void main(String[] args) {
        final String PALINDROME =
            "(?x) | (?:(.) add)+ chk"
                .replace("add", assertEntirety(".*? (\\1 \\2?)"))
                .replace("chk", assertEntirety("\\2"));

        System.out.println(PALINDROME);
        // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)

        String[] tests …