当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。

发表于: 2012-04-17   作者:bylijinnan   来源:转载   浏览:
摘要: public class CommonSubSequence { /** * 题目:写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。 * 写一个版本算法复杂度O(N^2)和一个O(N) 。 * * O(N^2):对于a中的每个字符,遍历b中的每个字符,如果相同,则拷贝到新字符串中。 * O(

public class CommonSubSequence {

	/**
	 * 题目:写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。
	 * 写一个版本算法复杂度O(N^2)和一个O(N) 。
	 * 
	 * O(N^2):对于a中的每个字符,遍历b中的每个字符,如果相同,则拷贝到新字符串中。
	 * O(N):首先使用b中的字符建立一个hash_map,对于a中的每个字符,检测hash_map中是否存在,如果存在则拷贝到新字符串中。
	 * 
	 * we do the O(N).
	 * commonSubSequence(String strA,String strB).
	 * 1.In java,"char" is 16 bits.So we make 'int[] count=new int[65536]'.
	 * If a char('x',e.g) shows up in "strB",we set count['x']=1
	 * 2.Now we iterate "strA".For each char in "strA",'y' for example,
	 * if count['y']=1,we add 'y' to the result sequence.
	 * 3.To avoid duplicate char,we set  count['y']=0 after adding 'y' to result sequence.
	 * 
	 */
	private static final int SIZE=Character.SIZE;
	public static void main(String[] args) {
		String a="#abcdefgaaa";
		String b="lmnopcxbyacccc";
		String c=commonSubSequence(a,b);//abc
		System.out.println(c);
	}

	// return the common sequence of string 'a' and string 'b'.In the order of string 'a'
	public static String commonSubSequence(String a,String b){
		if(a==null||b==null||a.length()==0||b.length()==0){
			return null;
		}
		int[] c=new int[1<<SIZE];//char[65536].Is it too large?
		char min=Character.MIN_VALUE;
		char[] x=a.toCharArray();
		char[] y=b.toCharArray();
		char[] z=new char[a.length()];//the result char sequence
		
		for(int i=0,len=y.length;i<len;i++){
			int pos=y[i]-min;
			c[pos]=1;
		}
		int j=0;
		for(int i=0,len=x.length;i<len;i++){
			int pos=x[i]-min;
			if(c[pos]==1){
				c[pos]=0;
				z[j++]=x[i];
			}
		}
		
		return new String(z,0,j);
	}
	
}

java-写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
[leetcode] https://leetcode.com/problems/shortest-word-distance/ For example, Assume that wor
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中, 则字符串一称之为字
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中, 则字符串一称之为字
DP的方式求解: #include <iostream> using namespace std; #define M 9 #define N 11 //如果
转载地址:http://blog.csdn.net/shandianling/article/details/7913818 这与求两个字符串的公共子
这与求两个字符串的公共子序列要区分开,见http://blog.csdn.net/shandianling/article/details/788
最长公共子串(LCS),有三种情况:1.公共子串的元素必须相邻. 2.公共子串的元素可以不相邻联单3. 求多
问题是这样的,假设连个线性表La和Lb分别表示两个集合A和B(即线性表中的数据元素即为集合中的成员)
用数组名作参数 代码: /* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 文
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号