首页 > ACM题库 > 九度OJ > 九度-1168-字符串的查找删除[解题代码]
2013
12-13

九度-1168-字符串的查找删除[解题代码]

题目来源:2009年北京航空航天大学计算机研究生机试真题

题目描述:

给定一个短字符串(不含空格),再给定若干字符串,在这些字符串中删除所含有的短字符串。

输入:

输入只有1组数据。
输入一个短字符串(不含空格),再输入若干字符串直到文件结束为止。

输出:

删除输入的短字符串(不区分大小写)并去掉空格,输出。

样例输入:
in
#include 
int main()
{

printf(" Hi ");
}
样例输出:
#clude
tma()
{

prtf("Hi");
}
提示:

注:将字符串中的In、IN、iN、in删除。


java 代码如下:
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		Pattern p = Pattern.compile("in", Pattern.CASE_INSENSITIVE);
		String ss = s.nextLine();
		while(s.hasNextLine()){
			String str = s.nextLine();
			Matcher m  = p.matcher(str);
			str = m.replaceAll("");
			str = str.replaceAll(" +", "");
			System.out.println(str);
		}
	}

}

/**************************************************************
	Problem: 1168
	User: coder
	Language: Java
	Result: Accepted
	Time:160 ms
	Memory:16004 kb
****************************************************************/


  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)