文档章节

求字符串列表中最长公子串

milin
 milin
发布于 2014/12/15 23:34
字数 526
阅读 23
收藏 0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 求N个字符串中的最大公子串 思路:先找出字符串中最短的那个字符串,然后依次取出最短字符串中的每个字符与其余字符串进行比较。
 */
public class ShortString {
	// 定义字符串的比较器(根据长度比较)
	private class LengthComparator implements Comparator<String> {
		@Override
		public int compare(String str1, String str2) {
			if (str1.length() < str2.length())
				return -1;
			else if (str1.length() == str2.length())
				return 0;
			else if (str1.length() > str2.length())
				return 1;
			return 0;
		}
	}

	// 字符串列表中的最短字符串
	public String minStr(Collection<String> strings) {
		return Collections.min(strings, new LengthComparator());
	}

	// 判断字符串列表中的每个字符串是否包含指定字符串,如果有一个不包含就返回false
	public boolean contains(ArrayList<String> strings, String str) {
		for (String s : strings) {
			if (!s.contains(str))
				return false;
		}
		return true;
	}

	// 最短公共字符串
	public String maxSubString(ArrayList<String> strings) {
		String maxStr = "";// 最长公子串
		String tempStr = "";// 临时变量
		String minStr = minStr(strings);// 所有字符串中的最短字符串
		/**
		 * 思路:
		 * 1.先获得所有字符串中的最短的字符串
		 * 2.然后截取最短字符串(从长到短),例如abcd,截取顺序abcd,abc,ab,a,bcd,bc,b,cd,c,d
		 * 3.将截取后的最短字符串与列表中的所有字符串比较
		 */
		for (int i = 0; i < minStr.length(); i++) {
			//如果最所剩字符数小于最长公子串长度,就直接进入跳出循环。
			//	例如:minStr ="abcd",maxStr="ab";那么就没有必要再遍历cd及cd的子串了
			if (maxStr.length() < minStr.length() - i) {
				for (int j = minStr.length(); j >= i; j--) {
					tempStr = minStr.substring(i, j);
					//如果截取的临时字符串长度 <= 最长公子串的长度,就没有必要再执行循环了,因为接下来的循环只能使临时字符串越来越短
					if (tempStr.length() <= maxStr.length())
						break;//结束内循环,跳到外循环
					if (contains(strings, tempStr)) {
						if (tempStr.length() > maxStr.length()) {
							maxStr = tempStr;
						}
					}
				}
			}else 
				break;
		}
		return maxStr;
	}

	public static void main(String[] args) {
		ArrayList<String> strings = new ArrayList<String>(Arrays.asList(
				"abdfdfabf", "abcabdeftdsfgsdg","abdcdefsdf"));
		ShortString ss = new ShortString();
		System.out.println("字符串列表:" + strings);
		System.out.println("最短字符串:" + ss.minStr(strings));
		System.out.println("最长公子串:" + ss.maxSubString(strings));
	}
}

本文转载自:http://blog.csdn.net/afgasdg/article/details/7019317

milin
粉丝 10
博文 94
码字总数 19598
作品 0
郑州
高级程序员
私信 提问
无重复字符的最长子串[双指针+哈希表] LeetCode.3

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "bbbbb" 输...

我不是张小毛
08/20
0
0
你需要的LeeCode题No.03——“无重复字符的最长子串”_一点课堂(多岸学院)

无重复字符的最长子串 题目:无重复字符的最长子串 描述:给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。 示例: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串...

程伟鑫
09/11
16
0
定义一个栈的数据结构,实现min函数,要求push,pop,min时间复杂度是0(1);找出字符串中的最长子串,要求子串不含重复字符,时间复杂度是O(n);

1.将IPV4转换成整数,要求高效。 2.定义一个栈的数据结构,实现min函数,要求push,pop,min时间复杂度是0(1); 3.数组a[n]里存有1到n的所有数,除了一个数removed,找出这个missing的数。 4.找...

Yason_Luo
2014/03/07
483
0
马拉车算法(Manacher's Algorithm)

这是悦乐书的第343次更新,第367篇原创 Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间...

小川94
06/04
0
0
Leetcode3——Longest Substring Without Repeating Characters

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given a string, find the length of the longest substring without repeating characters. Examples: 2. 求解 方法一 当遍......

Quincuntial
2017/04/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CRM、DMP、CDP都是什么?有什么区别?

Markter对CRM系统(Customer Relationship Management System,客户关系管理系统),营销自动化等概念都已经比较熟悉,也许DMP(Data Management Platform,数据管理平台)也多多少少有些了解。...

怡海软件-CRM
4分钟前
0
0
中台是什么,到底要解决什么问题?

故事的开始 这个最早由阿里在2015年提出的“大中台,小前台”战略中延伸出来的概念,最近在国内大热。阿里、腾讯、百度、京东、美团、滴滴等一众互联网巨头,从去年到今年,接连开始组织架构...

喵二狸
16分钟前
1
0
Linux Centos 7 - MySQL 5.7离线安装

内部网络通过离线包的方式进行安装。 一、下载 下载地址:https://dev.mysql.com/downloads/mysql/ 进入页面后,点击右侧链接。 下载对应版本。 通过xftp6等工具上传到服务器上。 二、安装和...

华山猛男
16分钟前
1
0
EventBus 3 全解

EventBus 3 全解 [TOC] 使用 一个基于观察者模式的事件发布/订阅框架. 用于模块间通信和解耦, 使用方便,性能高. 基本使用 1. gradle导入依赖库 implementation 'org.greenrobot:eventbus:3....

马湖村第九后羿
18分钟前
1
0
HTTP 协议

什么是HTTP协议? HTTP是hypertext transport protocol的缩写,即超文本传输协议。 是用于万维网服务器与本地浏览器之间传输超文本的传送协议。可以使浏览器更加高效,使网络传输减少。能够保...

彩色泡泡糖
29分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部