面试算法知识梳理(3) - 字符串算法第二部分

作者: 泽毛 | 来源:发表于2017-11-06 21:11 被阅读209次

面试算法知识梳理(5) - 数组第二部分
面试算法知识梳理(1) - 排序算法
面试算法知识梳理(4) - 数组第一部分
面试算法知识梳理(3) - 字符串算法第二部分
面试算法知识梳理(2) - 字符串算法第一部分
面试算法知识梳理(6) - 数组第三部分
面试算法知识梳理(14) - 数字算法
面试算法知识梳理(11) - 二叉树算法第一部分
面试算法知识梳理(9) - 链表算法第一部分
面试算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列

一、概要

本文介绍了有关字符串的算法第二部分的Java代码实现，所有代码均可通过在线编译器直接运行，算法目录：

查找字符串中的最长重复子串
求长度为N的字符串的最长回文子串
将字符串中的*移到前部，并且不改变非*的顺序
不开辟用于交换的空间，完成字符串的逆序C++
最短摘要生成
最长公共子序列

二、代码实现

2.1 查找字符串中的最长重复子串

问题描述

给定一个文本文件作为输入，查找其中最长的重复子字符串。例如，"Ask not what your country can do for you, but what you can do for your country"中最长的重复字符串是“can do for you”，第二长的是"your country"。

解决思路

这里解决问题的时候用到了 后缀数组 的思想，它指的是字符串所有右子集的集合，例如字符串abcde，它的后缀数组就为["abcde", "bcde", "cde", "de", "e"]。

解法分为三步：

求得输入字符串p的后缀数组，把它存放在一个List当中，这里注意去掉空格的情况。
对List中的所有元素进行快速排序。快速排序的目的不在于使得整个数组有序，而在于 使得前缀差异最小的两个字符串在数组中位于相邻的位置，对于上面的例子，其排序结果为：

后缀数组的快速排序结果

遍历排序后的数组，只需要对数组中的 相邻的两个元素 从头开始比较，计算出这两个字符串相同前缀的长度。遍历之后，取得的最大值就是最长重复子串的长度，而这两个字符串的相同前缀就是最长重复子串。

实现代码

import java.util.ArrayList;
import java.util.List;
import java.lang.String;

class Untitled {

    static void quickSortStr(List<String> c, int start, int end){
        if(start >= end)
            return;
        int pStart = start;
        int pEnd = end;
        int pMid = start;
        String t = null;
        for (int j = pStart+1; j <= pEnd; j++) {
            if ((c.get(pStart)).compareTo(c.get(j)) > 0) {
                pMid++;
                t = c.get(pMid); 
                c.set(pMid, c.get(j)); 
                c.set(j, t);
            }
        }
        t = c.get(pStart); 
        c.set(pStart, c.get(pMid)); 
        c.set(pMid, t);
        quickSortStr(c, pStart, pMid-1);
        quickSortStr(c, pMid+1, pEnd);
    }
    
    //获得两个字符串从第一个字符开始，相同部分的最大长度。
    static int comLen(String p1, String p2){
        int count = 0;
        int p1Index = 0;
        int p2Index = 0;
        while (p1Index < p1.length()) {
            if (p1.charAt(p1Index++) != p2.charAt(p2Index++))
                return count;
            count++;
        }
        return count;
    }

    static String longComStr(String p, int length){
        List<String> dic = new ArrayList<String>();
        int ml = 0 ;
        for (int i = 0; i < length; i++) {
            if (p.charAt(i) != ' ') {
                //构造所有的后缀数组。
                dic.add(p.substring(i, p.length()));
            }
        }
        String mp = null;
        //对后缀数组进行排序。
        quickSortStr(dic, 0, dic.size()-1);
        //打印排序后的数组用于调试。
        for (int i = 0; i < dic.size(); i++) {
            System.out.println("index=" + i + ",data=" + dic.get(i));
        }
        for (int i = 0; i < dic.size()-1; i++) {
            int tl = comLen(dic.get(i), dic.get(i+1));
            if (tl > ml) {
                ml = tl;
                mp = dic.get(i).substring(0, ml);
            }
        }
        return mp;
    } 

    public static void main(String[] args) {
        String source = "Ask not what your country can do for you, but what you can do for your country";
        System.out.println("result = " + longComStr(source, source.length()));
    }
}

运行结果

>> result = can do for you

2.2 求长度为 N 的字符串的最长回文子串

问题描述

长度为N的字符串，求这个字符串里的最长回文子串，回文字符串 简单来说就是一个字符串正着读和反着读是一样的。

解决思路

这里用到的是Manacher算法，首先需要对原始的字符串进行预处理，即在每个字符之间加上一个标志位，这里用#来表示，这会使得对于任意一个输入，经过处理后的字符串长度为2*len+1，也就是说 处理后的字符串始终为奇数。

在上面我们已经介绍过，回文串中最左或最右位置的字符与其对称轴的距离称为 回文半径，Manacher定义了一个数组RL[i]，它表示 第i个字符为对称轴的回文串 的 最右一个字符与字符i的闭区间所包含的字符个数，以google为例，经过处理后的字符串为#g#o#o#g#l#e，那么RL[i]的值为：

而RL[i]-1的值就是原始字符串中，以位置i为对称轴的最长回文串的长度，那么接下来的问题就变成如何计算RL[i]数组。

首先，我们需要两个辅助的变量maxidR和maxid，它表示当前计算的回文字符串中，所能触及到的最右位置，而maxid则表示该回文串的对称轴所在位置，而RL[maxid]为该回文串的距离。

假设我们此时遍历到了第i个字符，那么这时候有两种情况：

(1) i < maxidR

在这种情况下，我们知道p[maxid+1, .., maxid+RL[maxid]-1]和p[maxid-1, .., maxid-RL[maxid]+1]部分是关于p[maxid]对称的，利用这个有效信息，可以避免一些不必要的判断。

现在，我们获得i关于maxid的对称点j，这个点位于maxid的左侧，因此，我们已经计算过以它为中心的回文字符串长度RL[j]，对于以p[j]为中心的回文字符串有两种情况：

以j为中心的回文字符的最左边j-(RL[j]-1) 大于等于 maxidR关于maxid的对称点maxid-(maxidR-maxid)，在这种情况下，我们可以推断出以i为对称点的RL[i]的值最小为RL[j]。
大于的情况，可以保证以i为对称点的RL[i]至少为(maxidR-i)+1。

当然这上面只是推测出的 最小情况，之后仍然要继续遍历来更新RL[i]的值。

(2) i >= maxidR

这时候没有任何的已知信息，我们只能从i的左右两边慢慢遍历。

实现代码

class Untitled {
    
    static int maxSynStr(char ip[], int len) {
        int size = 2*len + 1;
        char a[] = new char[size];
        int RL[] = new int[size];
        int i = 0;
        int n;
        while (i < len) {
            a[(i<<1)+1] = ip[i];
            a[(i<<1)+2] = '#';
            i++;
        }
        a[0] = '#';
        //最远字符的中心对称点。
        int maxid = 0;
        //探索到的最远字符。
        int maxidR = 0;
        int ans = 0;
        RL[0] = 1;
        for (i = 1; i < size; i++) {
            //首先推测出i为中心的最小回文半径。
            int offset = 0;
            if (i < maxidR) {
                //j是关于maxid在左边的对称点。
                int j = maxid-(i-maxid);
                //获取之前计算出的以j为中心的回文半径。
                if (j-(RL[j]-1) >= maxid-(maxidR-maxid)) {
                    offset = RL[j]-1;
                } else {
                    offset = maxidR-maxid;
                } 
            }
            do {
                offset++;
            } while(i-offset >= 0 && i+offset < size && a[i+offset] == a[i-offset]);
            //最后一次是匹配失败的，因此要减去1。
            offset--;
            //RL[i]的值包括了自己，因此要加1。
            RL[i] = offset+1;
            //更新当前最大的回文半径。
            if (i+offset > maxidR){
                maxidR = i+offset;
                maxid = i;
            }
            if (RL[i] > ans) {
                ans = RL[i];
            }
        }
        return ans-1;
    } 
    
    public static void main(String[] args) {
        char[] source = "google".toCharArray();
        System.out.println("result=" + maxSynStr(source, 6));
    }
}

运行结果：

>> result=4

2.3 将字符串中的 * 移到前部，并且不改变非 * 的顺序

问题描述

将字符串中的*移到前部，并且不改变非*的顺序，例如ab**cd**e*12，处理后为*****abcde12。

解决思路

我们可以将整个数组分为两个部分：有可能包含*字符的部分和一定不包含*字符的部分。初始时候，整个数组只有有 有可能包含*字符的部分，那么我们就可以 从后往前 遍历，每遇到一个非*的字符就把它放到 一定不包含*字符的部分，由于需要保持非*的顺序，因此需要将它插入到该部分的首部。

实现代码

class Untitled {

    static void moveNullCharPos(char p[], int length) {
        if (length > 1) {
            char t;
            char c;
            int lastCharIndex = length;
            //必须要从后向前扫描。
            for(int j = length-1; j >=0 ;j--) {
                if ((c = p[j]) != '*') {
                    lastCharIndex--;
                    t = p[lastCharIndex]; p[lastCharIndex] = p[j]; p[j] = t;
                }
            }
        }
        System.out.println(p);
    }

    public static void main(String[] args) {
        char[] source = "ab**cd**e*12".toCharArray();
        moveNullCharPos(source, source.length);
    }
}

运行结果：

>> *****abcde12

2.4 不开辟用于交换的空间，完成字符串的逆序（C++）

问题描述

不开辟用于交换的空间，完成字符串的逆序。

解决思路

这里利用的是 两次亦或等于本身 的思想。

实现代码

#include <iostream>
using namespace std;

void reverWithoutTemp(char *p, int length){
    int i = 0;
    int j = length-1;
    while (i < j) {
        p[i] = p[i]^p[j];  
        //实际上是p[i]^p[j]^p[j]，这里的p[i]和p[j]指的是原始数组中的值。
        p[j] = p[i]^p[j];  
        //实际上是(p[i]^(p[i]^p[j]^p[j]))^(p[i]^p[j]^p[j])，这里的p[i]和p[j]指的是原始数组中的值。
        p[i] = p[i]^p[j];  
        i++;j--;
    }
    std::cout << p << std::endl;
}

int main() {
    char p[] = "1234566";
    reverWithoutTemp(p, 7);
    return 0;
}

运行结果：

>> 6654321

2.5 最短摘要生成

问题描述

给定一段描述w和一组关键字q，我们从这段描述中找出包含所有关键字的最短字符序列，这个最短字符序列就称为 最短摘要：

最短字符序列必须包含所有的关键字
最短字符序列中关键字的顺序可以是随意的

解决思路

假设我们的输入序列如下所示，其中w表示非关键字的字符串，而q则表示关键字的字符串：

w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

这里，我们引入额外的三个变量pStart、pEnd和flag数组，flag数组用于统计pStart和pEnd之间关键字的命中情况。

这里说明一下flag数组的作用，flag数组和关键字p数组的长度相同，每命中一个关键字，就将flag数组的对应位置+1，而flagSize只有在每次遇到一个新的关键字时才更新，因此它表示flag数组中 不重复的关键字的个数。

算法的步骤如下：

第一步：我们将pEnd从w[0]开始移动，每发现一个命中的关键字，就更新flag[]数组，直到w[pStart,..,pEnd] 包含了所有的关键字，即w0,w1,w2,w3,q0,w4,w5,q1。
第二步：开始移动pStart，这时候pStart,..,pEnd之间的长度将会逐渐变短，在移动的过程中，同时更新flag[]数组，直到pStart,...,pEnd之间 不再包含所有的关键字，这时候就可以求得 目前为止的最短摘要长度，即q0,w4,w5,q1。
第三步：重复第一步的操作，移动pEnd使得pStart,...,pEnd重新 包含所有的关键字，再执行第二步的操作来 更新最短摘要长度，直到pEnd遍历到w的最后一个元素。

实现代码

class Untitled {

    static int findKey(String[] p1, String p2) {
        int len = p1.length;
        for(int i = 0; i < len; i++) {
            if(p1[i].equals(p2))
                return i;
        }
        return -1;
    }
    
    //p1为原始数据，p2为所有的关键词。
    static int calMinAbst(String[] p1, String[] p2) {
        int p1Len = p1.length;
        int p2Len = p2.length;
        int r;
        int shortAbs = Integer.MAX_VALUE;
        int tAbs = 0;
        int pBegin = 0;
        int pEnd = 0;
        int absBegin = 0;
        int absEnd = 0;
        int flagSize = 0;
        int flag[] = new int[p2Len];
        //初始化标志位数组。
        for (int i = 0; i < p2Len; i++) {
            flag[i] = 0;
        }
        while (pEnd < p1Len) {
            //只有先找到全部的关键词才退出循环。
            while (flagSize != p2Len && pEnd < p1Len) {
                r = findKey(p2, p1[pEnd++]);
                if (r != -1) {
                    if (flag[r] == 0) {
                        flagSize++;
                    }
                    flag[r]++;
                }
            }
            while (flagSize == p2Len) {
                if ((tAbs = pEnd-pBegin) < shortAbs) {
                    shortAbs = tAbs;
                    absBegin = pBegin;
                    absEnd = pEnd-1;
                }
                r = findKey(p2, p1[pBegin++]);
                if (r != -1) {
                    flag[r]--;
                    if (flag[r] == 0) {
                        flagSize--;
                    }
                }
            }
        }
        for (int i = absBegin; i <= absEnd; i++) {
            System.out.print(p1[i] + ",");
        }
        System.out.println("\n最短摘要长度=" + tAbs);
        return shortAbs;
    }

    public static void main(String[] args) {
        String keyword[] = {"微软", "计算机", "亚洲"};
        String str[] = { 
            "微软","亚洲","研究院","成立","于","1998","年","，","我们","的","使命",
            "是","使","未来","的","计算机","能够","看","、","听","、","学","，",
            "能","用","自然语言","与","人类","进行","交流","。","在","此","基础","上",
            "，","微软","亚洲","研究院","还","将","促进","计算机","在","亚太","地区",
            "的","普及","，","改善","亚太","用户","的","计算","体验","。","”"
        };
        calMinAbst(str, keyword);
    }
}

运行结果

>> 微软,亚洲,研究院,还,将,促进,计算机,
>> 最短摘要长度=7

2.6 最长公共子序列

问题描述

经典的LCS问题，这里主要解释一下最长公共子序列的含义。最长公共子串和最长公共子序列的区别：子串是 串的一个连续的部分，子序列则是 不改变序列的顺序，而从序列中去掉任意的元素 而获得的新序列。

解决思路

经典的LCS问题，原理可以参考这篇被广泛转载的文章程序员编程艺术第十一章：最长公共子序列问题，这里给出简要介绍一下基本的思想。

LCS基于下面这个定理：

LCS 算法定理
最终目的是构建类似于下面的一个矩阵：

LCS 矩阵

对于矩阵，定义c[i][j]：它表示字符串序列A的前i个字符组成的序列A和字符串序列B的前j个字符组成的序列B之间的最长公共子序列的长度，其中i<=A.len，并且j<=B.len。
如果A[i]=B[j]，那么A与B之间的最长公共子序列的最后一项一定是这个元素，也就是c[i][j] = c[i-1][j-1]+1。
如果A[i]!=B[j]，则c[i][j]= max(c[i-1][j], c[i][j-1])。
初始值为：c[0][j]=c[i][0]=0。

代码实现

class Untitled {

    static void LCS(char a[], int aLen, char b[], int bLen){
        int c[][] = new int[bLen+1][aLen+1];
        for (int i = 1; i < bLen+1; i++) {
            for (int j = 1; j < aLen+1; j++) {
                if (a[j-1] == b[i-1]) {
                    c[i][j] = c[i-1][j-1] + 1;
                } else {
                    c[i][j] = (c[i-1][j]>c[i][j-1]) ? c[i-1][j]:c[i][j-1];
                }
            }
        }
        int csl = c[bLen][aLen];
        char p[] = new char[csl+1];
        int i = bLen, j = aLen;
        while (i > 0 && j > 0 && c[i][j] > 0) {
            if (c[i][j] == c[i-1][j]) {
                i--;
            } else if(c[i][j] == c[i][j-1]) {
                j--;
            } else if(c[i][j] > c[i-1][j-1]) {
                p[c[i][j]] = a[j-1];
                i--;j--;
            }
        }
        for (i = 1; i <= csl; i++) {
            System.out.print(p[i]);
        }
    } 

    public static void main(String[] args) {
        char p1[] = "aadaae".toCharArray();
        char p2[] = "adaaf".toCharArray();
        LCS(p1, p1.length, p2, p2.length);
    }
}

运行结果

>> adaa

网友评论

本文标题：面试算法知识梳理(3) - 字符串算法第二部分

本文链接：https://www.haomeiwen.com/subject/evghmxtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

面试算法知识梳理(3) - 字符串算法第二部分

面试算法代码知识梳理系列

一、概要

二、代码实现

2.1 查找字符串中的最长重复子串

问题描述

解决思路

实现代码

运行结果

2.2 求长度为 N 的字符串的最长回文子串

问题描述

解决思路

(1) i < maxidR

(2) i >= maxidR

实现代码

运行结果：

2.3 将字符串中的 * 移到前部，并且不改变非 * 的顺序

问题描述

解决思路

实现代码

2.4 不开辟用于交换的空间，完成字符串的逆序（C++）

问题描述

解决思路

实现代码

运行结果：

2.5 最短摘要生成

问题描述

解决思路

实现代码

运行结果

2.6 最长公共子序列

问题描述

解决思路

代码实现

运行结果

更多文章，欢迎访问我的 Android 知识梳理系列：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读