Learn-Algorithms/9 Algorithms Job Interview/1 字符串.md

# 字符串

字符串常见的问题：

* 回文判断
* 字符(串)统计
* [子串查找](1.1%20字符串-查找.md)
* [字符串修改](1.3%20字符串-修改.md) 如单词反转/移动等
* [字符删除](1.2%20字符串-删除.md)  
* 字符串的压缩  
* 字符串的排列和组合 


## Java 字符串处理 常用 API

```
String  
charAt(index)
char[]
Map<Character,Integer>
```


## 判断字符串是否是回文

> 回文，如 abcdcba

分析: 2个指针，一头一尾，逐个比较，都相同就是回文

```
/*
* eg acdeedca
* @ret 0 success , -1 fail
*/
int is_huiwen(const char *source){
	if (source == NULL || source == '\0') return -1;
	char *head = source;
	char *tail = source;
	while(*tail != '\0'){
		tail++;
	}
	tail--;

	while(head < tail){
		if (*head != *tail){
			return -1;
		}
		head++;
		tail--;
	}

	return 0;
}
```



## 统计文章里单词出现的次数

设计相应的数据结构和算法，尽量高效的统计一片英文文章（总单词数目）里出现的所有英文单词，按照在文章中首次出现的顺序打印输出该单词和它的出现次数。

```
void statistics(char *string)
void statistics(FILE *fd)
```

 
延伸：  

如果是海量数据里面统计top-k次数的单词呢？  



## 实现字符串转整型的函数

也就是实现函数atoi的功能，这道题目考查的就是对各种情况下异常处理。比如:  

以`213`分析转换成证书的过程。`3+1x10+2x100` ，思路是：每扫描到一个字符，把 `之前得到的数字*10`，再加上当前的数字

* 0开头，"0213"
* 正/负数，"-432" ,"--422","++23"  
* 浮点数，"43.2344"   
* 非法,"2123des"  
* 存在空格，"  -32","  +432","  234","23  432","353  ","  + 321"  
* NULL/空串，这时候返回值0  
* 溢出，"32111111112222222222222222222222222222222" , 与 `INT_MAX `比较  
* 如何区分正常的'0'和异常情况下返回的结果"0"? 可以通过一个全局变量 g_status 来标示，值为 kValid/kInvalid。



```
int atoi(const char *str){
	
}
```

详细过程也可以[参考这里](http://blog.csdn.net/v_july_v/article/details/9024123)




## 匹配兄弟字符串  

什么是兄弟字符串？

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。

思路：判断各自素数乘积是否相等。更多方法请参见：http://blog.csdn.net/v_JULY_v/article/details/6347454。

```
int isBrother(const char *first,const char *secd)
```

思路一： 循环匹配 指数级复杂度  
思路二： 利用质数，平方和比较，但这样必须是2个串的长度要一样，需要的空间比较大，最多256个字节。



示例代码：

```
int isBrother(const char *first,const char *secd){
	
}
```

 

## 字符串的排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。输入字符串 abcca，则输出由 a，b，c排列出来的所有字符串,字符出现个数不变


分析：这是一道很好的考查对递归理解的编程题

简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，还有逆序生成排列和一些不需要递归生成排列的方法。

>印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。



## n个字符串联接

有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。




## 字符串的集合合并

给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。