# 笔试题—字符串常见的算法题集锦

• KMP算法
• 字母倒序输出
• 全排列
• 全组合

## KMP算法

### 代码如下

```package com.xujun.stringfind;

public class KMPFind {

public static void main(String[] args) {
String s = "abcbb2abcabx";
String c = "abca";
int[] next = new int[s.length() + 1];
next = getNext(c);
for (int i = 0; i < next.length; i++) {
System.out.println("=" + next[i]);
}
int find = matchNext(s, c, 0);
System.out.println("find=" + find);

int[] nextVal = getNextVal(c);

for (int i = 0; i < nextVal.length; i++) {
System.out.println("=" + nextVal[i]);
}
int matchNextVal = matchNextVal(s, c, 0);
System.out.println("matchNextVal=" + matchNextVal);

}

/**
* 注意这里为了保持保持一致性 ，第一个next[0]没有用到
*
* @param c
* @return
*/
private static int[] getNextVal(String c) {
int[] nextVal = new int[c.length() + 1];
int front = 0;
int behind = 1;
nextVal[1] = 0;
/**
* c.charAt(front-1)表示前缀字符 ，c.charAt(behind-1)表示后缀字符
*/
while (behind < c.length()) {
if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
++front;
++behind;
if (c.charAt(front - 1) != c.charAt(behind - 1)) {
nextVal[behind] = front;
} else {
nextVal[behind] = nextVal[front];
}
} else {
// 前缀索引回溯
front = nextVal[front];
}
}

return nextVal;
}

/**
* 注意这里为了保持保持一致性 ，第一个next[0]没有用到
*
* @param c
* @return
*/
private static int[] getNext(String c) {
int[] next = new int[c.length() + 1];
int front = 0;
int behind = 1;
next[1] = 0;
/**
* c.charAt(front-1)表示前缀字符 c.charAt(behind-1)表示后缀字符
*/
while (behind < c.length()) {
if (front == 0 || c.charAt(front - 1) == c.charAt(behind - 1)) {
++front;
++behind;
next[behind] = front;
} else {
// 前缀 索引回溯
front = next[front];
}
}

return next;
}

public static int matchNextVal(String source, String c, int pos) {

int i;
int[] nextVal = getNextVal(c);
if (pos < 1) {
i = 1;
} else {
i = pos + 1;
}
int j = 1; // i控制S,j控制T;
while (i <= source.length() && j <= c.length()) {
if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
++i;
++j;
} else {
j = nextVal[j]; // j退回合适的位置，i值不变
}
}
if (j > c.length())
return i - c.length() - 1;
else
return -1;
}

public static int matchNext(String source, String c, int pos) {

int i;
int[] next = getNext(c);
if (pos < 1) {
i = 1;
} else {
i = pos + 1;
}
int j = 1; // i控制S,j控制T;
while (i <= source.length() && j <= c.length()) {
if (j == 0 || source.charAt(i - 1) == c.charAt(j - 1)) {
++i;
++j;
} else {
j = next[j]; // j退回合适的位置，i值不变
}
}
if (j > c.length())
return i - c.length() - 1;
else
return -1;
}

}```

## 字符串倒序输出，单词不倒序

### 思路解析

• 1.我们可以采用正则表达式把字符串分隔成为字符串数组
• 2.接着我们再倒序输出字符串数组
• 3.在注意最后一个字符串数组，可能是空格
```public class ReverseStr2 {

public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.nextLine();
String[] strArray = str.split("[^a-zA-Z]+");
for (int i = strArray.length - 1; i >= 2; i--) {
System.out.print(strArray[i] + ' ');
}
// 如果字符串数组的第一个元素是空串，那么下标为1的元素就是最后一个要输出的元素，末尾不要再加空格
if (strArray[0].length() == 0)
System.out.println(strArray[1]);
else
System.out.println(strArray[1] + ' ' + strArray[0]);
}
}

}```

### 思路解析

• 对输入的字符串进行分析，去掉非法字符，如中文字符，多个空格只保留一个空格等
• 对字符串进行分组
• 倒序输出

### 代码如下

```/**
* Created by xujun on 2016/9/20
*/
public class ReverseStr {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
StringBuilder sb = new StringBuilder();
String[] a = filter(sc.nextLine()).split(" ");
sb.append(a[a.length - 1]);
for (int i = a.length - 2; i >= 0; i--) {
sb.append(" " + a[i]);
}

System.out.println(sb.toString().trim());
}
}

public static String filter(String s) {
char[] c = s.toCharArray();
StringBuilder sb = new StringBuilder();
boolean isFirstSpace=true;
for (int i = 0; i < c.length; i++) {
if ((c[i] >= 'a' && c[i] <= 'z') || (c[i] >= 'A' && c[i] <= 'Z')) {
sb.append(c[i]);
isFirstSpace=true;
continue;
}
if(isFirstSpace){
sb.append(' ');
isFirstSpace=false;
}

}
return sb.toString();
}
}```

## 字符串全排列

### 思路分析

• 从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，
• 从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例：
• 固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
• 固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
• 固定c，求后面ba的排列：cba，cab。
```public class permutate {
public static int total = 0;
public static void swap(String[] str, int i, int j)
{
String temp = new String();
temp = str[i];
str[i] = str[j];
str[j] = temp;
}
public static void arrange (String[] str, int st, int len)
{
if (st == len - 1)
{
for (int i = 0; i < len; i ++)
{
System.out.print(str[i]+ "  ");
}
System.out.println();
total++;
}
else
{
for (int i = st; i < len; i ++)
{
swap(str, st, i);
arrange(str, st + 1, len);
swap(str, st, i);
}
}

}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str[] = {"a","b","c"};
arrange(str, 0, str.length);
System.out.println(total);
}
}```

a b c d a b d c a c b d a c d b a d c b a d b c b a c d b a d c b c a d b c d a b d c a b d a c c b a d c b d a c a b d c a d b c d a b c d b a d b c a d b a c d c b a d c a b d a c b d a b c 24

## 全组合

### 第一种方法

#### 思路解析

000,001,010,011,100,101,110,111

```public static  void Combination( ) {
/*基本思路：求全组合，则假设原有元素n个，则最终组合结果是2^n个。原因是：
* 用位操作方法：假设元素原本有：a,b,c三个，则1表示取该元素，0表示不取。故去a则是001，取ab则是011.
* 所以一共三位，每个位上有两个选择0,1.所以是2^n个结果。
* 这些结果的位图值都是0,1,2....2^n。所以可以类似全真表一样，从值0到值2^n依次输出结果：即：
* 000,001,010,011,100,101,110,111 。对应输出组合结果为：
空,a, b ,ab,c,ac,bc,abc.
这个输出顺序刚好跟数字0~2^n结果递增顺序一样
取法的二进制数其实就是从0到2^n-1的十进制数
* ******************************************************************
* *
* */
String[] str = {"a" , "b" ,"c"};
int n = str.length;                                  //元素个数。
//求出位图全组合的结果个数：2^n
int nbit = 1<<n;                                     // “<<” 表示 左移:各二进位全部左移若干位，高位丢弃，低位补0。:即求出2^n=2Bit。
System.out.println("全组合结果个数为："+nbit);

for(int i=0 ;i<nbit ; i++) {                        //结果有nbit个。输出结果从数字小到大输出：即输出0,1,2,3,....2^n。
System.out.print("组合数值  "+i + " 对应编码为： ");
for(int j=0; j<n ; j++) {                        //每个数二进制最多可以左移n次，即遍历完所有可能的变化新二进制数值了
int tmp = 1<<j ;
if((tmp & i)!=0) {                            //& 表示与。两个位都为1时，结果才为1
System.out.print(str[j]);
}
}
System.out.println();
}
}```

### 第二种方法

#### 思路解析

n个元素选m个元素的组合问题的实现. 原理如下:

• 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可;
• 2) 如果不包含5, 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可;
• 3) 如果也不包含4, 直接选取3, 那么再在前2个里面选取2个, 刚好只有两个.
• 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m.
• 横向看, 该问题为一个前i-1个中选m-1的递归.

### 代码如下

```package com.xujun.PermutationCombinationHolder;

public final class PermutationCombinationHolder {

/** 数组元素的全组合 */
static void combination(char[] chars) {
char[] subchars = new char[chars.length]; // 存储子组合数据的数组
// 全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加
// 上选n个元素的组合的和
for (int i = 0; i < chars.length; ++i) {
final int m = i + 1;
combination(chars, chars.length, m, subchars, m);
}
}

/**
* n个元素选m个元素的组合问题的实现. 原理如下: 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个. 如: 1, 2, 3, 4,
* 5 中选取3个元素. 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可; 2) 如果不包含5,
* 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可; 3) 如果也不包含4, 直接选取3,
* 那么再在前2个里面选取2个, 刚好只有两个. 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m. 横向看,
* 该问题为一个前i-1个中选m-1的递归.
*/
static void combination(char[] chars, int n, int m, char[] subchars,
int subn) {
if (m == 0) { // 出口
for (int i = 0; i < subn; ++i) {
System.out.print(subchars[i]);
}
System.out.println();
} else {
for (int i = n; i >= m; --i) { // 从后往前依次选定一个
subchars[m - 1] = chars[i - 1]; // 选定一个后
combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
}
}
}

/** 数组元素的全排列 */
static void permutation(char[] chars) {
permutation(chars, 0, chars.length - 1);
}

/** 数组中从索引begin到索引end之间的子数组参与到全排列 */
static void permutation(char[] chars, int begin, int end) {
if (begin == end) { // 只剩最后一个字符时为出口
for (int i = 0; i < chars.length; ++i) {
System.out.print(chars[i]);
}
System.out.println();
} else {
for (int i = begin; i <= end; ++i) { // 每个字符依次固定到数组或子数组的第一个
if (canSwap(chars, begin, i)) { // 去重
swap(chars, begin, i); // 交换
permutation(chars, begin + 1, end); // 递归求子数组的全排列
swap(chars, begin, i); // 还原
}
}
}
}

static void swap(char[] chars, int from, int to) {
char temp = chars[from];
chars[from] = chars[to];
chars[to] = temp;
}

static boolean canSwap(char[] chars, int begin, int end) {
for (int i = begin; i < end; ++i) {
if (chars[i] == chars[end]) {
return false;
}
}
return true;
}

public static void main(String[] args) {
final char[] chars = new char[] { 'a', 'b', 'c' };
permutation(chars);
System.out.println("===================");
combination(chars);
}
}```

## 题外话

• 已经有20多天没更新博客了，主要是因为家里有事，回家了十来天，最近又在校招，有时候参加宣讲会与招聘，有时候在准备笔试和面试的东西。
• 现在还没有拿到offer，也是感觉挺可惜的。
• 接下来更新博客的频率可能会比较不稳定

101 篇文章26 人订阅

0 条评论

## 相关文章

### 请问你知道什么是栈吗？

1.1栈的概念及记本操作 栈(stack)又称堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行...

3138

2333

1304

### Scala第一章学习笔记

面向对象编程是一种自顶向下的程序设计方法。用面向对象方法构造软件时，我们将代码以名词（对象）做切割，每个对象有某种形式的表示服(self/this)、行为（...

1052

561

### Java 关于集合框架那点事儿

1.引入集合框架   采用数组存在的一些缺陷：    1.数组长度固定不变，不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

29110

上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理，但是这种集合类型虽然可以随机访问数据，但是如果需要删除中间的元素就...

2025

1074

4225

### 合法的出栈序列

poj 1363 Rails 已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中 停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序...

812