首页 > 代码库 > 131. Palindrome Partitioning
131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab"
,
Return
[ ["aa","b"], ["a","a","b"]]
典型的backtracking题目。需要一个函数来判断是否为回文序列,然后s从头至尾,如果前面的是回文序列,则recursive到s的后半部分。
public IList<IList<string>> Partition(string s) { var res = new List<IList<string>>(); if(s =="") return res; Backtracking(s,res,new List<string>()); return res; } private void Backtracking(string s, List<IList<string>> res , List<string> cur) { if(s == "") { res.Add(new List<string>(cur)); } else { for(int i =1;i<= s.Length;i++) { if(IsPalindrome(s.Substring(0,i))) { cur.Add(s.Substring(0,i)); Backtracking(s.Substring(i),res,cur); cur. RemoveAt(cur.Count()-1); } } } } private bool IsPalindrome(string s) { if(s == null) return false; var c = s.ToCharArray(); Array.Reverse(c); return s == new string(c); }
131. Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。