草庐IT

关于算法：Java：如何通过插入最少字符数来创建字符串的最短回文？

codeneng 2023-03-28 原文

Java: How to create the shortest palindrome of a string by inserting the minimum number of characters?

我目前有以下实现，它通过插入最少数量的字符来处理给定字符串的最短回文，但只处理前面的字符插入以创建最短回文。

但是通过以下实现，或者如果有更好的实现，我该如何在字符串中的任何点插入字符以使其成为回文？

将接受并投票赞成答案。谢谢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Answer {
    public String findShortestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        int i = len - 1;
        for (; i >= 0; --i) {
            if (stringIsPalindrome(s, 0, i)) {
                break;
            }
        }

        StringBuilder sb = new StringBuilder(s.substring(i + 1));
        sb.reverse().append(s);
        return sb.toString();
    }

    public boolean stringIsPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

差异
寻找处理插入字符串中任意点的最短回文。

  • 这听起来像家庭作业。
  • 以最少的插入将字符串转换为回文字符串的可能重复项

你可以试试这个解决方案。这应该有效！

1
2
3
4
5
6
7
8
9
10
11
public boolean stringIsPalindrome(String s, int start, int end) {

    String str1 = s.substring(0,Math.floor((end-start)/2));
    String str2 = s.substring(Math.floor((end-start)/2),end);
    str2 = reverseString(str2);
    return str1.equals(str2);
}

public String reverseString(String s) {
            //YOUR REVERSE STRING METHOD
    }

  • 我不认为这是乔所要求的。此外，您的 stringIsPalindrome 实际上比他的原始方法慢，因为它创建了一个额外的字符串，反转其中一个字符串，然后比较它们。
  • 抱歉！我只是提出一个可能的解决方案

你可以实现以下蛮力算法：

  • 如果输入字符串为空或由一个元素组成，则返回输入
  • 如果字符串的第一个字符等于最后一个字符，则将该过程应用于输入字符串，没有第一个和最后一个项目

  • 如果 first 和 last 不一样，那么你有两个选择：

    1
    2
    left = last + palindromed(input without last) + last  or
    right = first + palindromed(input without first) + first

    所以在这一步你选择最短的解决方案

    • 在我接受答案并投票之前，为澄清起见，您能否举一个我迄今为止实施的示例？谢谢

    数来回文spanclassnbspalgorithmdynamic-programmingjavapalindrome

    有关关于算法：Java：如何通过插入最少字符数来创建字符串的最短回文？的更多相关文章

    1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

      我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

    2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

      总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

    3. Ruby 解析字符串 - 2

      我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么？我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等，你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算，还是有更好的方法？也许为此目的准备了一个开箱即用的库？

    4. ruby - 如何在 Ruby 中顺序创建 PI - 2

      出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

    5. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

      我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

    6. ruby-on-rails - unicode 字符串的长度 - 2

      在我的Rails(2.3，Ruby1.8.7)应用程序中，我需要将字符串截断到一定长度。该字符串是unicode，在控制台中运行测试时，例如'א'.length，我意识到返回了双倍长度。我想要一个与编码无关的长度，以便对unicode字符串或latin1编码字符串进行相同的截断。我已经了解了Ruby的大部分unicode资料，但仍然有些一头雾水。应该如何解决这个问题？ 最佳答案 Rails有一个返回多字节字符的mb_chars方法。试试unicode_string.mb_chars.slice(0,50)

    7. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

      关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

    8. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

      给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

    9. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

      我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

    10. ruby - 将差异补丁应用于字符串/文件 - 2

      对于具有离线功能的智能手机应用程序，我正在为Xml文件创建单向文本同步。我希望我的服务器将增量/差异(例如GNU差异补丁)发送到目标设备。这是计划:Time=0Server:hasversion_1ofXmlfile(~800kiB)Client:hasversion_1ofXmlfile(~800kiB)Time=1Server:hasversion_1andversion_2ofXmlfile(each~800kiB)computesdeltaoftheseversions(=patch)(~10kiB)sendspatchtoClient(~10kiBtransferred)Cl

    随机推荐