C#，回文分割问题（Palindrome Partitioning Problem）算法与源代码

  • 开发
  • 19

1 回文串

“回文串”是一个正读和反读都一样的字符串，初始化标志flag=true，比如“level”或者“noon”等等就是回文串。

2 回文分割问题

给定一个字符串，如果该字符串的每个子字符串都是回文的，那么该字符串的分区就是回文分区。
例如，“aba | b | bbabb | a | b | aba”是“abababababa”的回文分区。
确定给定字符串的回文分区所需的最少切割。
例如，“ababababababa”至少需要3次切割。
 这三个分段是“a | babbab | b | ababa”。
如果字符串是回文，则至少需要0个分段。
如果一个长度为n的字符串包含所有不同的字符，则至少需要n-1个分段。

3 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class Algorithm_Gallery
    {
        #region 算法1
        private static bool PPP_IsPalindrome(string String, int i, int j)
        {
            while (i < j)
            {
                if (String[i] != String[j])
                {
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }

        public static int Min_Palindrome_Partion(string str, int i, int j)
        {
            if (i >= j || PPP_IsPalindrome(str, i, j))
            {
                return 0;
            }
            int ans = Int32.MaxValue, count;
            for (int k = i; k < j; k++)
            {
                count = Min_Palindrome_Partion(str, i, k) + Min_Palindrome_Partion(str, k + 1, j) + 1;

                ans = Math.Min(ans, count);
            }
            return ans;
        }
        #endregion

        #region 算法2
        public static int Min_Palindrome_Partion(string str)
        {
            int n = str.Length;
            int[,] C = new int[n, n];
            bool[,] P = new bool[n, n];

            int i, j, k, L;
            for (i = 0; i < n; i++)
            {
                P[i, i] = true;
                C[i, i] = 0;
            }

            for (L = 2; L <= n; L++)
            {
                for (i = 0; i < n - L + 1; i++)
                {
                    j = i + L - 1;
                    if (L == 2)
                    {
                        P[i, j] = (str[i] == str[j]);
                    }
                    else
                    {
                        P[i, j] = (str[i] == str[j]) && P[i + 1, j - 1];
                    }
                    if (P[i, j] == true)
                    {
                        C[i, j] = 0;
                    }
                    else
                    {
                        C[i, j] = int.MaxValue;
                        for (k = i; k <= j - 1; k++)
                        {
                            C[i, j] = Math.Min(C[i, j], C[i, k] + C[k + 1, j] + 1);
                        }
                    }
                }
            }
            return C[0, n - 1];
        }
        #endregion

        #region 算法3
        public static int Min_Cutting(string a)
        {
            int[] cut = new int[a.Length];
            bool[,] palindrome = new bool[a.Length, a.Length];
            for (int i = 0; i < a.Length; i++)
            {
                int minCut = i;
                for (int j = 0; j <= i; j++)
                {
                    if (a[i] == a[j] && (i - j < 2 || palindrome[j + 1, i - 1]))
                    {
                        palindrome[j, i] = true;
                        minCut = Math.Min(minCut, j == 0 ? 0 : (cut[j - 1] + 1));
                    }
                }
                cut[i] = minCut;
            }
            return cut[a.Length - 1];
        }
        #endregion

        #region 算法4
        public static int Min_Palindrome_Partion_Second(string str)
        {
            int n = str.Length;
            int[] C = new int[n];
            bool[,] P = new bool[n, n];

            int i, j, L;
            for (i = 0; i < n; i++)
            {
                P[i, i] = true;
            }

            for (L = 2; L <= n; L++)
            {
                for (i = 0; i < n - L + 1; i++)
                {
                    j = i + L - 1;
                    if (L == 2)
                    {
                        P[i, j] = (str[i] == str[j]);
                    }
                    else
                    {
                        P[i, j] = (str[i] == str[j]) && P[i + 1, j - 1];
                    }
                }
            }

            for (i = 0; i < n; i++)
            {
                if (P[0, i] == true)
                {
                    C[i] = 0;
                }
                else
                {
                    C[i] = int.MaxValue;
                    for (j = 0; j < i; j++)
                    {
                        if (P[j + 1, i] == true && 1 + C[j] < C[i])
                        {
                            C[i] = 1 + C[j];
                        }
                    }
                }
            }
            return C[n - 1];
        }
        #endregion

        #region 算法5
        private static string PPP_Hashcode(int a, int b)
        {
            return a.ToString() + "" + b.ToString();
        }

        public static int Min_Palindrome_Partiion_Memoizatoin(string input, int i, int j, Hashtable memo)
        {
            if (i > j)
            {
                return 0;
            }
            string ij = PPP_Hashcode(i, j);
            if (memo.ContainsKey(ij))
            {
                return (int)memo[ij];
            }

            if (i == j)
            {
                memo.Add(ij, 0);
                return 0;
            }
            if (PPP_IsPalindrome(input, i, j))
            {
                memo.Add(ij, 0);
                return 0;
            }
            int minimum = Int32.MaxValue;

            for (int k = i; k < j; k++)
            {
                int left_min = Int32.MaxValue;
                int right_min = Int32.MaxValue;
                string left = PPP_Hashcode(i, k);
                string right = PPP_Hashcode(k + 1, j);

                if (memo.ContainsKey(left))
                {
                    left_min = (int)memo[left];
                }
                if (memo.ContainsKey(right))
                {
                    right_min = (int)memo[right];
                }

                if (left_min == Int32.MaxValue)
                {
                    left_min = Min_Palindrome_Partiion_Memoizatoin(input, i, k, memo);
                }
                if (right_min == Int32.MaxValue)
                {
                    right_min = Min_Palindrome_Partiion_Memoizatoin(input, k + 1, j, memo);
                }
                minimum = Math.Min(minimum, left_min + 1 + right_min);
            }

            memo.Add(ij, minimum);

            return (int)memo[ij];
        }
        #endregion
    }
}
 

POWER BY TRUFFER.CN 

4 源代码

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class Algorithm_Gallery
    {
        #region 算法1
        private static bool PPP_IsPalindrome(string String, int i, int j)
        {
            while (i < j)
            {
                if (String[i] != String[j])
                {
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }

        public static int Min_Palindrome_Partion(string str, int i, int j)
        {
            if (i >= j || PPP_IsPalindrome(str, i, j))
            {
                return 0;
            }
            int ans = Int32.MaxValue, count;
            for (int k = i; k < j; k++)
            {
                count = Min_Palindrome_Partion(str, i, k) + Min_Palindrome_Partion(str, k + 1, j) + 1;

                ans = Math.Min(ans, count);
            }
            return ans;
        }
        #endregion

        #region 算法2
        public static int Min_Palindrome_Partion(string str)
        {
            int n = str.Length;
            int[,] C = new int[n, n];
            bool[,] P = new bool[n, n];

            int i, j, k, L;
            for (i = 0; i < n; i++)
            {
                P[i, i] = true;
                C[i, i] = 0;
            }

            for (L = 2; L <= n; L++)
            {
                for (i = 0; i < n - L + 1; i++)
                {
                    j = i + L - 1;
                    if (L == 2)
                    {
                        P[i, j] = (str[i] == str[j]);
                    }
                    else
                    {
                        P[i, j] = (str[i] == str[j]) && P[i + 1, j - 1];
                    }
                    if (P[i, j] == true)
                    {
                        C[i, j] = 0;
                    }
                    else
                    {
                        C[i, j] = int.MaxValue;
                        for (k = i; k <= j - 1; k++)
                        {
                            C[i, j] = Math.Min(C[i, j], C[i, k] + C[k + 1, j] + 1);
                        }
                    }
                }
            }
            return C[0, n - 1];
        }
        #endregion

        #region 算法3
        public static int Min_Cutting(string a)
        {
            int[] cut = new int[a.Length];
            bool[,] palindrome = new bool[a.Length, a.Length];
            for (int i = 0; i < a.Length; i++)
            {
                int minCut = i;
                for (int j = 0; j <= i; j++)
                {
                    if (a[i] == a[j] && (i - j < 2 || palindrome[j + 1, i - 1]))
                    {
                        palindrome[j, i] = true;
                        minCut = Math.Min(minCut, j == 0 ? 0 : (cut[j - 1] + 1));
                    }
                }
                cut[i] = minCut;
            }
            return cut[a.Length - 1];
        }
        #endregion

        #region 算法4
        public static int Min_Palindrome_Partion_Second(string str)
        {
            int n = str.Length;
            int[] C = new int[n];
            bool[,] P = new bool[n, n];

            int i, j, L;
            for (i = 0; i < n; i++)
            {
                P[i, i] = true;
            }

            for (L = 2; L <= n; L++)
            {
                for (i = 0; i < n - L + 1; i++)
                {
                    j = i + L - 1;
                    if (L == 2)
                    {
                        P[i, j] = (str[i] == str[j]);
                    }
                    else
                    {
                        P[i, j] = (str[i] == str[j]) && P[i + 1, j - 1];
                    }
                }
            }

            for (i = 0; i < n; i++)
            {
                if (P[0, i] == true)
                {
                    C[i] = 0;
                }
                else
                {
                    C[i] = int.MaxValue;
                    for (j = 0; j < i; j++)
                    {
                        if (P[j + 1, i] == true && 1 + C[j] < C[i])
                        {
                            C[i] = 1 + C[j];
                        }
                    }
                }
            }
            return C[n - 1];
        }
        #endregion

        #region 算法5
        private static string PPP_Hashcode(int a, int b)
        {
            return a.ToString() + "" + b.ToString();
        }

        public static int Min_Palindrome_Partiion_Memoizatoin(string input, int i, int j, Hashtable memo)
        {
            if (i > j)
            {
                return 0;
            }
            string ij = PPP_Hashcode(i, j);
            if (memo.ContainsKey(ij))
            {
                return (int)memo[ij];
            }

            if (i == j)
            {
                memo.Add(ij, 0);
                return 0;
            }
            if (PPP_IsPalindrome(input, i, j))
            {
                memo.Add(ij, 0);
                return 0;
            }
            int minimum = Int32.MaxValue;

            for (int k = i; k < j; k++)
            {
                int left_min = Int32.MaxValue;
                int right_min = Int32.MaxValue;
                string left = PPP_Hashcode(i, k);
                string right = PPP_Hashcode(k + 1, j);

                if (memo.ContainsKey(left))
                {
                    left_min = (int)memo[left];
                }
                if (memo.ContainsKey(right))
                {
                    right_min = (int)memo[right];
                }

                if (left_min == Int32.MaxValue)
                {
                    left_min = Min_Palindrome_Partiion_Memoizatoin(input, i, k, memo);
                }
                if (right_min == Int32.MaxValue)
                {
                    right_min = Min_Palindrome_Partiion_Memoizatoin(input, k + 1, j, memo);
                }
                minimum = Math.Min(minimum, left_min + 1 + right_min);
            }

            memo.Add(ij, minimum);

            return (int)memo[ij];
        }
        #endregion
    }
}

阅读全部

相关推荐

  3. 面试算法94：最少回文分割

    2024-03-12 01:24:03       43 阅读

  5. C语言入门算法——回文数

    2024-03-12 01:24:03       13 阅读

  10. 【算法】分割回文串【动态规划】【回溯】

    2024-03-12 01:24:03       36 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-03-12 01:24:03       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-03-12 01:24:03       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-03-12 01:24:03       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-03-12 01:24:03       20 阅读

热门阅读

  1. 【Stable Diffusion】入门：AI绘画提示词+参数设置攻略

    2024-03-12 01:24:03       61 阅读

  2. 【Spring Boot单元测试】讲解

    2024-03-12 01:24:03       17 阅读

  7. Spring反序列化失败 Type definition error: [simple type, class xxx.xxx.xxx]

    2024-03-12 01:24:03       17 阅读

  10. Day 9. TCP并发模型、select、poll、epoll

    2024-03-12 01:24:03       22 阅读

  23. 笔记75：使用 git_pull 更新已经安装过的 ROS 软件包

    2024-03-12 01:24:03       23 阅读

  30. 【SQL实用技巧】-- join系列

    2024-03-12 01:24:03       20 阅读