字符串回文實現

hzc 發布于2019-08-16 16:06 / 3161人閱讀

摘要：字符串回文如何判斷一個字符串是否是回文字符串的問題，我想你應該聽過，我們今天的思題目就是基于這個問題的改造版本。

字符串回文

如何判斷一個字符串是否是回文字符串的問題，我想你應該聽過，我們今天的思題目就是基于這個
問題的改造版本。如果字符串是通過單鏈表來存儲的，那該如何來判斷是一個回文串呢？你有什么
好的解決思路呢？相應的時間空間復雜度又是多少呢？

思路：
1.使用快慢指針來找到中間節點
2.在找中間節點的同時復制一份反序的從開頭到中間節點的鏈表prev
3.比較prev鏈表和slow鏈表是否相同

代碼：

package me.study.algorithm;

/**
 * public class LinkNode {
 *
 *     char val;
 *
 *     LinkNode next;
 *
 *     public LinkNode() {
 *     }
 *
 *     public LinkNode(char val) {
 *         this.val = val;
 *     }
 * }
 */
public class StringBack {


    public boolean clac(LinkNode head) {

        if (head.next == null && head.next == null){
            return true;
        }

            LinkNode prev = null;
            LinkNode slow = head;
            LinkNode fast = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                LinkNode next = slow.next;
                slow.next = prev;
                prev = slow;
                slow = next;
            }


            if (fast != null) {
                slow = slow.next;
            }

            while (slow != null) {
                if (slow.val != prev.val) {
                    return false;
                }
                slow = slow.next;
                prev = prev.next;
            }

            return true;


    }
}

最好時間復雜度：
最好的情況就是單個字符或者空字符串，時間復雜度為O(1)

最壞時間復雜度：
查找中間節點時間復雜度n/2
比較大小時間復雜度直到最后才比較出是否相等所以為n/2
相加起來最后的時間復雜度為O(n)

云服務器 GPU云服務器回文字符串 python實現回文回文字符串算法c語言判斷回文字符c語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73898.html

最長回文子串——Manacher 算法

摘要：問題定義最長回文子串問題給定一個字符串，求它的最長回文子串長度。可以采用動態規劃，列舉回文串的起點或者終點來解最長回文串問題，無需討論串長度的奇偶性。 0. 問題定義最長回文子串問題：給定一個字符串，求它的最長回文子串長度。如果一個字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 評論0 收藏0
[算法總結] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規方法。如果不存在公共前綴，返回空字符串。注意假設字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
[Leetcode] Palindrome Permutation 回文變換

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結果中是否有回文。而中心對稱點如果是字符，該字符會是奇數次，如果在兩個字符之間，則所有字符都是出現偶數次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 評論0 收藏0
java算法題：最長回文串

摘要：給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構造成的最長的回文串。比如不能當做一個回文字符串。注意假設字符串的長度不會超過。代碼實現最長回文串回文串是一個正讀和反讀都一樣的字符串，比如或者等等就是回文串。 LeetCode: 給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構造成的最長的回文串。在構造過程中，請注意區分大小寫。比如Aa不能當做一個回文字符串。注意:...

Honwhy 2019-08-19 11:47 評論0 收藏0
獲取最長回文子串

摘要：以下是最長回文子串的相關代碼，相關邏輯已在注釋中注明我們原有的字符串可能存在兩種回文子串，一種是具有基數個元素例如一種是具有偶數個元素例如這樣的話分情況判斷比較復雜所以我們對原字符串進行擴充在相鄰元素中插入特殊值插入后的原基數回文子串變成了以下是最長回文子串的Manacher‘s Algorithm相關代碼，相關邏輯已在注釋中注明： public static String solu...

ymyang 2019-08-19 11:46 評論0 收藏0