- 浏览: 247498 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
mabusyao:
漠北空城 写道请问下,你这个是JDK版本是多少呢?!忘记了,应 ...
HashMap 源码解读 -
漠北空城:
请问下,你这个是JDK版本是多少呢?!
HashMap 源码解读 -
schumee:
完美团队~
项目沉思录 - 1.1 -
winie:
整理下 搞成引擎嘛 国产需要这样的engine
简单工作流引擎 -
mabusyao:
某位同学给我提供的堪称完美的解决方案:1. 将三个int数组放 ...
CraneWork
package palindrome;
/*Problem Statement
A palindrome is a string that reads the same forward and backward.
A palindrome substring is a contiguous sequence of characters taken from a string that form a palindrome.
A palindrome substring of a string is maximal if we can't extend it to get a bigger palindrome substring.
For example, string "acdadc" has 2 maximal palindrome substrings - "a" (the first one) and "cdadc".
All other palindrome substrings (like "dad" or "c") can be extended to "cdadc", so they are not maximal.
You will be given a String[] str.
Concatenate the elements of str to form one long string, and return the number of maximal palindrome substrings contained in that string.
Definition
Class: MaximalPalindromeSubstrings
Method: countMaximalPalindromeSubstrings
Parameters: String[]
Returns: int
Method signature: int countMaximalPalindromeSubstrings(String[] str)
(be sure your method is public)
Constraints
- str will contain between 1 and 50 elements, inclusive.
- Each element of str will contain between 1 and 50 characters, inclusive.
- Each character of each element of str will be a lowercase letter ('a'-'z').
Examples
0) {"acdadc"} Returns: 2 The example from the problem statement.
1) {"ababab"} Returns: 2 The two maximal palindrome substrings here are "ababa" and "babab".
2) {"aaaa","bbb","axxx"} Returns: 3 Remember to use the whole input!
3) {"abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh"} Returns: 14
This problem statement is the exclusive and proprietary property of TopCoder, Inc.
Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved. */
public class MaximalPalindromeSubstrings {
public static int countMaximalPalindromeSubstrings(String[] str) {
int length = 0;
for(int i = 0; i < str.length; i++) {
length = length + str[i].length();
}
char[] array = new char[length];
int p = 0;
for(int i = 0; i < str.length; i++) {
char[] tempArray = str[i].toCharArray();
for(int j = 0; j < tempArray.length; j++) {
array[p] = tempArray[j];
p++;
}
}
p = 0;
while(p<length) {
int index = 0;
while(p - index >=0 && p + index < length) {
if(array[p - index] == array[p + index]) index++;
else break;
}
index--;
save(p - index, p + index);
index = 0;
if((p + 1 < length) && (array[p] == array[p + 1])) {
while(p - index >=0 && p + 1 + index < length) {
if(array[p - index] == array[p + 1 + index]) index++;
else break;
}
index--;
save(p - index, p + 1 + index);
}
p++;
}
print(array);
return root -1;
}
// Stack for the result storage.
private static Pair[] result = new Pair[100];
private static int root = 0;
static class Pair {
int start = 0;
int end = 0;
Pair(int i, int j) {
start = i;
end = j;
}
}
/*
* Check if there is a larger ranger or smaller range.
* Erase the smaller range if needed.
*/
private static void save(int i, int j) {
if(root == 0) {
Pair pair = new Pair(i, j);
result[0] = pair;
root++;
}
else {
int cursor = root - 1;
if (result[cursor].start <= i && result[cursor].end >= j) return;
while(cursor >= 0) {
if(result[cursor].start >= i && result[cursor].end <= j) {
cursor--;
result[root - 1] = null;
root--;
}
else break;
}
Pair pair = new Pair(i, j);
result[root] = pair;
root++;
}
}
/*
* print the result out.
*/
private static void print(char[] array) {
for(int i = 0; i < root; i++) {
for(int j = result[i].start; j <= result[i].end; j++) {
System.out.print(array[j]);
}
System.out.print("\n");
}
}
}
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
try {
String[] a = {"aaaa","bbb","axxx"};
String b = "abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh";
MaximalPalindromeSubstrings.countMaximalPalindromeSubstrings(new String[]{b});
} catch(Exception e) {
e.printStackTrace();
}
}
}
发表评论
-
大数据下的实体解析
2016-07-07 12:03 671大数据时代的实体解析困境 <!--[if !sup ... -
中文相似度匹配算法
2015-12-30 14:44 1921基于音形码的中文字 ... -
各种语言写的wordcount
2015-09-24 16:07 0Java版本: String input ... -
数组双指针算法的研究
2015-07-14 16:59 2418双指针算法在数组/链 ... -
摩尔投票法
2015-06-30 20:13 18275摩尔投票法 提问: 给定一个int型数组,找出该数 ... -
(转)最长回文字串算法
2015-01-18 14:30 1395来自(http://blog.163.com/zhaohai ... -
STRUTS2 源码 - Logging System
2012-05-24 08:51 1357看了STRUTS2的源码,了解了它的logging系统,觉得还 ... -
在线词典的数据结构实现。
2012-05-18 08:37 0昨天在网上看到了一道百度的面试题: Baidu写道 ... -
存储中间计算结果的动态规划算法
2012-04-18 15:50 1178public class RodCutting { ... -
java写的四则运算器
2011-08-19 22:19 2660本打算做一个从RE到NFA的转换器,思路已经理清了,但是在动手 ... -
什么是最小二乘拟合
2007-09-14 21:27 923对于一个数据点(x1, y1), ... (xn, yn)的集 ... -
CraneWork
2008-07-14 19:14 952/*Problem Statement There are ... -
SalesRouting
2008-07-15 10:53 739package salesRouting;/*Problem ... -
FactorialSystem
2008-07-21 19:36 817/*Problem StatementIn the facto ... -
RecurringNumbers
2008-07-22 09:41 882/*Problem StatementA rational n ... -
HardDuplicateRemover
2008-07-23 15:17 878/*Problem StatementWe have a se ... -
BlockStructure
2008-07-23 20:55 760/*Problem StatementA group of v ... -
SkipStones
2008-07-28 17:31 790/*Problem StatementWhen a stone ... -
TheaterVisit
2008-07-28 17:31 741/*Problem StatementYou want to ... -
SquareDigits
2010-07-06 12:36 990Problem Statement ***Note: ...
相关推荐
北大POJ1159-Palindrome 解题报告+AC代码
C++实现的Palindrome,回文 C++实现的Palindrome,回文
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
Palindrome Sub-Array,Problem Description A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-...
北大POJ1159-Palindrome
C#,回文分割问题(Palindrome Partitioning Problem)算法与源代码 1 回文串 “回文串”是一个正读和反读都一样的字符串,初始化标志flag=true,比如“level”或者“noon”等等就是回文串。 2 回文分割问题 给定...
palindrome22.in
LeetCode Palindrome Number解决方案
检查字符串是否为palindrome, 从前后分别检查,并计算出相同或不同的数量。
palindrome_prime.c
JAVA程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构
palindrome(STACK,QUEUE).cpp
palindrome number in c
GET /java-palindrome-example/palindrome/ 解析提供的字符串,并找到其中包含的最大回文。 在此情况下,也可以将type的可选查询参数设置为slow在这种情况下,服务将使用慢得多的递归算法。 例子 GET /java-...
安装要安装bencreating_palindrome ,请将此行添加到应用程序的Gemfile : gem 'bencreating_palindrome'然后安装如下: $ bundle install或者直接使用gem安装它: $ gem install bencreating_palindrome用法...
回文数Java
资源来自pypi官网。 资源全名:check-palindrome-kriti-0.0.1.tar.gz
正常来说暴力的思路是先匹配前缀pre和后缀suf,找到第一个不匹配的l和r,然后在由l开始从左向右求最长的回文串palindrome,以及由r开始从右向左求最长的回文串palindrome,那么pre+palindrome+suf就是答案。...