当前位置 : 主页 > 编程语言 > java >

Java C++题解leetcode字符串轮转KMP算法详解

来源:互联网 收集:自由互联 发布时间:2023-01-30
目录 题目要求 思路一:双指针(模拟) Java C++ 思路二:子串 手写KMP Java dp C++ dp 调API Java C++ 总结 题目要求 思路一:双指针(模拟) Java class Solution { public boolean isFlipedString(String s1,
目录
  • 题目要求
  • 思路一:双指针(模拟)
    • Java
    • C++
  • 思路二:子串
    • 手写KMP
      • Java
      • dp
      • C++
      • dp
    • 调API
      • Java
      • C++
  • 总结

    题目要求

    思路一:双指针(模拟)

    Java

    class Solution {
        public boolean isFlipedString(String s1, String s2) {
            if (s1.length() != s2.length())
                return false;
            int n = s1.length();
            if (n == 0)
                return true;
            for (int i = 0; i < n; i++) {
                boolean res = true;
                for (int j = 0; j < n; j++) {
                    if (s1.charAt((i + j) % n) != s2.charAt(j)) {
                        res = false;
                        break;
                    }
                }
                if (res)
                    return true;
            }
            return false;
        }
    }
    
    • 时间复杂度:O(n^2)
    • 空间复杂度:O(1)

    C++

    class Solution {
    public:
        bool isFlipedString(string s1, string s2) {
            if (s1.size() != s2.size())
                return false;
            int n = s1.size();
            if (n == 0)
                return true;
            for (int i = 0; i < n; i++) {
                bool res = true;
                for (int j = 0; j < n; j++) {
                    if (s1[(i + j) % n] != s2[j]) {
                        res = false;
                        break;
                    }
                }
                if (res)
                    return true;
            }
            return false;
        }
    };
    
    • 时间复杂度:O(n^2)
    • 空间复杂度:O(1)

    思路二:子串

    手写KMP

    KMP的思路可以参考KMP 算法详解和详解KMP算法

    Java

    get_next

    class Solution {
        public boolean isFlipedString(String s1, String s2) {
            if (s1.length() != s2.length())
                return false;
            int n = s1.length();
            if (n == 0)
                return true;
            int[] nxt = new int[n];
            nxt[0] = -1;
            int j = 0; // pat指针
            int k = -1; // 跳转位置
            while (j &lt; n - 1) {
                if (k == -1 || s2.charAt(j) == s2.charAt(k)) {
                    if (s2.charAt(++j) == s2.charAt(++k))
                        nxt[j] = nxt[k]; // 连续相同
                    else
                        nxt[j] = k;
                }
                else
                    k = nxt[k];
            }
            String txt = s1 + s1;
            j = 0;
            for (int i = 0; i &lt; 2 * n; i++) {
                if (j &lt; n &amp;&amp; txt.charAt(i) == s2.charAt(j))
                    j++;
                else {
                    j = nxt[j];
                    if (j == -1)
                        j++;
                }
                if (j == n)
                    return true;
            }
            return false;
        }
    }
    

    dp

    class Solution {
        public boolean isFlipedString(String s1, String s2) {
            if (s1.length() != s2.length())
                return false;
            int n = s1.length();
            if (n == 0)
                return true;
            int[][] dp = new int[n][256]; // dp[state][char] = nxt state
            dp[0][s2.charAt(0)] = 1;
            int x = 0; // 影子状态
            for (int s = 1; s < n; s++) {
                for (int c = 0; c < 256; c++)
                    dp[s][c] = dp[x][c];
                dp[s][s2.charAt(s)] = s + 1;
                x = dp[x][s2.charAt(s)];
            }
            String txt = s1 + s1;
            int state = 0;
            for (int i = 0; i < 2 * n; i++) {
                state = dp[state][txt.charAt(i)];
                if (state == n)
                    return true;
            }
            return false;
        }
    }
    
    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++

    get_next

    class Solution {
    public:
        bool isFlipedString(string s1, string s2) {
            if (s1.size() != s2.size())
                return false;
            int n = s1.size();
            if (n == 0)
                return true;
            int nxt[n];
            nxt[0] = -1;
            int j = 0; // pat指针
            int k = -1; // 跳转位置
            while (j < n - 1) {
                if (k == -1 || s2[j] == s2[k]) {
                    if (s2[++j] == s2[++k])
                        nxt[j] = nxt[k]; // 连续相同
                    else
                        nxt[j] = k;
                }
                else
                    k = nxt[k];
            }
            string txt = s1 + s1;
            j = 0;
            for (int i = 0; i < 2 * n; i++) {
                if (j < n && txt[i] == s2[j])
                    j++;
                else {
                    j = nxt[j];
                    if (j == -1)
                        j++;
                }
                if (j == n)
                    return true;
            }
            return false;
        }
    };
    

    dp

    class Solution {
    public:
        bool isFlipedString(string s1, string s2) {
            if (s1.size() != s2.size())
                return false;
            int n = s1.size();
            if (n == 0)
                return true;
            int dp[n][256]; // dp[state][char] = nxt state
            memset(dp, 0, sizeof(dp));
            dp[0][s2[0]] = 1;
            int x = 0; // 影子状态
            for (int s = 1; s < n; s++) {
                for (int c = 0; c < 256; c++)
                    dp[s][c] = dp[x][c];
                dp[s][s2[s]] = s + 1;
                x = dp[x][s2[s]];
            }
            string txt = s1 + s1;
            int state = 0;
            for (int i = 0; i < 2 * n; i++) {
                state = dp[state][txt[i]];
                if (state == n)
                    return true;
            }
            return false;
        }
    };
    
    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    调API

    Java

    class Solution {
        public boolean isFlipedString(String s1, String s2) {
            return s1.length() == s2.length() && (s1 + s1).contains(s2);
        }
    }
    
    • 时间复杂度:O(n),取决于语言匹配子字符串机制
    • 空间复杂度:O(n)

    C++

    class Solution {
    public:
        bool isFlipedString(string s1, string s2) {
            return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
        }
    };
    
    • 时间复杂度:O(n),取决于语言匹配子字符串机制
    • 空间复杂度:O(n)
    impl Solution {
        pub fn is_fliped_string(s1: String, s2: String) -> bool {
            s1.len() == s2.len() && s2.repeat(2).contains(&s1)
        }
    }
    
    • 时间复杂度:O(n),取决于语言匹配子字符串机制
    • 空间复杂度:O(n)

    总结

    做过了轮转的题就能很快意识到拼接然后找子串,本来调个API结束结果发现了KMP算法,就浅学一下~

    时间耗在算法了就掠过rust各种辣~

    以上就是Java C++题解leetcode字符串轮转KMP算法详解的详细内容,更多关于Java C++ 字符串轮转KMP算法的资料请关注自由互联其它相关文章!

    上一篇:Java DelayQueue实现任务延时示例讲解
    下一篇:没有了
    网友评论