`
mabusyao
  • 浏览: 257136 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

palindrome

阅读更多

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();
}

}
}

分享到:
评论

相关推荐

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    JAVA程序 Palindrome(回文?)

    JAVA程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构

    Pku acm 第1159题 Palindrome 代码

    Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划

    Palindrome Sub-Array

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

    C++实现的Palindrome,回文

    在编程领域,回文是一种特殊的字符串,它从前向后读和从后向前读是一样的,例如"madam"、"racecar"等。本主题主要关注如何使用C++语言来实现回文检测算法。C++作为一门强大的面向对象编程语言,提供了丰富的标准库和...

    huiwenshu.rar_palindrome

    最近,我接触了一个项目“huiwenshu.rar_palindrome”,该项目的目标是开发一个能够处理1-99999位数回文数判断的程序,同时,这个项目还涉及到了银行管理系统的部分功能,如利率计算、密码管理以及余额管理。...

    LeetCode9 Palindrome Number

    《LeetCode9:判断回文数——Java实现详解》 在编程的世界里,LeetCode是一个广受欢迎的在线平台,它提供了各种算法问题供程序员们挑战和提升技能。今天我们要探讨的是LeetCode第9题——“回文数”。...

    palindrome_soln.py

    在编程领域,尤其是Python学习和开发中,palindrome_soln.py文件是用于演示如何编写一个检测字符串是否为回文的程序。回文是指一个字符串从前往后读和从后往前读是完全相同的字符串。这个问题通常是编程初学者练习...

    PyPI 官网下载 | check-palindrome-kriti-0.0.1.tar.gz

    《PyPI官网下载:探索check-palindrome-kriti-0.0.1.tar.gz中的Python库知识》 PyPI(Python Package Index)是Python开发者的重要资源库,它提供了丰富的Python库供全球开发者下载和使用。本文将深入探讨标题为...

    java-leetcode题解之Palindrome Permutation.java

    今天,我们重点分析并解读题名为Palindrome Permutation(回文排列)的Java题解代码,这道题目是关于字符串处理的经典问题之一。 首先,我们需了解Palindrome Permutation问题的实质:给定一个字符串,判断该字符串...

    Stack3 java.rar_Stack3 java_palindrome

    标题中的"Stack3 java.rar_Stack3 java_palindrome"表明这是一个关于使用Java编程语言实现堆栈(Stack)数据结构,并且应用在判断回文(Palindrome)字符串上的项目。回文是指正读反读都能读通的字符串,如“level”...

    js-leetcode题解之125-valid-palindrome.js

    在探讨JavaScript编程语言以及LeetCode平台上的一道编程题目“Valid Palindrome”的解法时,我们需要了解几个关键点:JavaScript编程、数据结构与算法、以及字符串处理技巧。LeetCode是一个面向IT专业人员和学生的...

    java-leetcode题解之Palindrome Permutation II.java

    而“Palindrome Permutation II”是众多编程题目中的一道,它主要考察了程序员对字符串处理和排列组合的理解。在这道题目中,通常要求编写一个函数,该函数接受一个字符串作为输入,并返回该字符串所有可能的回文...

    回文数检测的Java实现方法PalindromeNumber.zip

    在Java中实现回文数检测,可以编写一个名为PalindromeNumber的类,并在其中定义一个方法比如isPalindrome,该方法接收一个整型参数并返回一个布尔值,表示该整数是否是回文数。在方法内部,根据上述逻辑来判断并返回...

    LeetCode Palindrome Number解决方案

    LeetCode Palindrome Number解决方案 在本节中,我们将讨论如何确定一个整数是否是一个回文数。一个整数是一个回文数当它从左到右读取和从右到左读取相同。 问题描述: 给定一个整数,判断它是否是一个回文数。 ...

    python-leetcode题解之234-Palindrome-Linked-List.py

    while is_palindrome and p2: if p1.val != p2.val: is_palindrome = False p1 = p1.next p2 = p2.next # Step 4 (可选): 恢复链表结构 prev = None current = second_half_head while current: next_...

    java-leetcode题解之Longest Chunked Palindrome Decomposition.java

    在LeetCode上,有一道题目叫做“Longest Chunked Palindrome Decomposition”,也就是“最长块状回文分解”。这个问题主要考察的是算法和编程能力,需要解决者了解回文(palindrome)这个概念。回文是指一个字符串...

    js-leetcode题解之131-palindrome-partitioning.js

    在JavaScript中,处理leetcode上的编程题目时,正确理解和解决"131.Palindrome Partitioning"这类字符串划分问题是一项重要的技能。本题要求编写一个函数,该函数将给定的字符串划分为尽可能多的回文子字符串,并...

    java-leetcode题解之Can Make Palindrome from Substring.java

    在深入探讨Java实现的LeetCode题解Can Make Palindrome from Substring的详细知识点之前,让我们先了解该题目的背景和要求。该题目要求编写一个Java方法,这个方法需要判断给定字符串的任何子串是否可以通过重新排列...

Global site tag (gtag.js) - Google Analytics