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);
}
}
分享到:
相关推荐
用一个函数实现两个字符串的比较,即自己写一个 strcmp 函数
C语言编程-编写函数fun求一个字符串的长度,在main函数中输入字符串,并输出其长度;
有两个字符串A,B,判断B是不是A的子串
字符串连接就是将一个字符串连接到另一个字符串的末尾,使其组合成一个新的字符串,在字符串处理函数中,strcat 函数具有字符串连接功能。下面是用C语言实现不使用是strcat 函数实现连接两个字符串的功能。 源代码:...
C语言编程-编写一个函数,该函数可以统计一个长度为2的字符串在另一个字符串中出现的次数;
字符串做函数参数,字符串copy函数技术推演,错误点等等
写自定义函数stringLower()实现将一个字符串中所有大写字母变为小写字母。在主函数中输入一含有大写字母的字符串,调用该函数并输出改变后的字符串。
JAVA字符串处理函数列表一览 JAVA字符串相关
305-字符串函数string.h应用举例(51单片机C语言实例Proteus仿真和代码)305-字符串函数string.h应用举例(51单片机C语言实例Proteus仿真和代码)305-字符串函数string.h应用举例(51单片机C语言实例Proteus仿真和代码)...
输入两个字符串,编一个程序实现strcmp()函数 #include #include #define N 100 main() { int i; char a[N],b[N]; printf("input a[] and b[]:\n"); gets(a); gets(b); for(i=0;i;i++) { if(a[i]==b[i])...
Linux下常用函数-字符串函数 Linux下常用函数-字符串函数 Linux下常用函数-字符串函数
C常用库函数-表 数学函数、字符函数、字符串函数、输入输出函数、动态分配函数和随机函数 C常用库函数-表 数学函数、字符函数、字符串函数、输入输出函数、动态分配函数和随机函数 C常用库函数-表 数学函数、字符...
传入一个字符串和该字符串的分割字符,返回去重后的字符串,可以直接在plsql中运行,简单的函数运用,能处理oracle中。资源仅供参考
JAVA字符串处理函数列表一览.txtJAVA字符串处理函数列表一览.txt
例如,如果我们有一个字符串"Hello World",那么len()函数将返回11,因为这个字符串有11个字符。 2. str()函数 str()函数用于将其他数据类型转换为字符串。例如,如果我们有一个整数10,我们可以使用str()函数将其...
StrComp StrComp(string1,string2[,compare]) 返回string1字符串与string2字符串的比较结果,如果两个字符串相同,则返回0,如果小于则返回-1,如果大于则返回1 InStr InStr(string1,string2[,compare]) 返回...
java中字符串常用函数 看了就知道 很好用 速查
int strarray cat char arr [str max len] int i char str 把二维arr字符串数组拼接成一个串 i是第一维的长度 存入str int replacate char res int n char const str 产生n个重复的str 串或者字符 存入res ">几个...
用c语言重写字符串功能函数,如字符串替换,即复制; 字符串比较
strcmp(char str1,char str2)//比较两个字符串大小str1>str2返回值>0,str1=str2返回值=0,str1返回值 strlen(char str)//返回字符串数据长度 strlwr(char str)//转换为小写 strupr(char str)//转换为大写