北京专业制作网站,seo优化技术教程,公司名称起名大全,德州乐陵德州seo公司1 回文串
“回文串”是一个正读和反读都一样的字符串#xff0c;初始化标志flagtrue#xff0c;比如“level”或者“noon”等等就是回文串。 2 回文分割问题
给定一个字符串#xff0c;如果该字符串的每个子字符串都是回文的#xff0c;那么该字符串的分区就是回文分区。… 1 回文串
“回文串”是一个正读和反读都一样的字符串初始化标志flagtrue比如“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 算法1private 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 算法2public 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 算法3public 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 算法4public 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 算法5private 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}
}
