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

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
    }
}