C3-字符串相关算法

2017-08-07

1 字符串面试题的特点

广泛性
1. 字符串可以看做字符类型的数组，与数组排序、查找、调整有关
2. 很多其他类型的面试题可以看做字符串类型的面试题

使用Java实现字符串类型的题目时，要掌握StringBuffer、StringBuilder、toCharArray方法。

需要掌握的概念
1. 回文
2. 子串（连续）
3. 子序列（不连续）
4. 前缀树（Trie树）
5. 后缀树和后缀数组
6. 匹配
7. 字典序
需要掌握的操作
1. 与数组有关的操作：增删改查
2. 字符的替换
3. 字符串的旋转

2 字符串题目的常见类型

规则判断
1. 判断字符串是否符合整数规则
2. 判断字符串是否符合浮点数规则
3. 判断字符串时候符合回文字符串规则
数字运算

int和long类型表达整数范围有限，所以经常用字符串实现大整数。
与大整数相关的加减乘除操作，需要模拟笔算的过程。
与数组操作有关的类型
1. 数组有关的调整、排序等操作需要掌握
2. 快速排序的划分过程需要掌握和改写
字符计数
1. 哈希表
2. 固定长度的数组 C/C++(256长度),Java（65535长度）
3. 滑动窗口问题、寻找无重复字符子串问题、计算变位词问题
动态规划
1. 最长公共子串
2. 最长公共子序列
3. 最长回文子串
4. 最长回文子序列
搜索类型
1. 宽度优先搜索
2. 深度优先搜索
高级算法与数据结构解决的问题
1. Manacher算法解决最长回文子串问题
2. KMP算法解决字符串匹配问题
3. 前缀树结构
4. 后缀树和后缀数组
5. 通常面试中很少出现

3 例题

例题1

普通解法

二叉树遍历 + 匹配问题
考察t1中以每个节点为头的子数是否与t2一致
假设t1树节点数为N，t2树节点数为M，最差时间复杂度为O(M*N)

最优解法

时间复杂度为O(M+N)
t1序列化->字符串str1，t2序列化->字符串str2
使用KMP算法判断str1中是否含有str2
- 如果str1中包含str2，说明t1中有与t2相同的子树
- 否则说明没有

代码实现

public boolean chkIdentical(TreeNode t1, TreeNode t2)
{
   StringBuilder sb1 = new StringBuilder();
   serializeTree(t1, sb1);
   StringBuilder sb2 = new StringBuilder();
   serializeTree(t2, sb2);
   if (sb1.toString().indexOf(sb2.toString()) != -1)
   {
       return true;
   }
   return false;
}
public void serializeTree(TreeNode t, StringBuilder sb)
{
   if (t == null)
   {
       sb.append("#!");
       return;
   }
   sb.append(t.val).append("!");
   if (t.left != null)
       serializeTree(t.left, sb);
   else
       sb.append("#!");
   if (t.right != null)
       serializeTree(t.right, sb);
   else
       sb.append("#!");
    }

例题2

普通方法

使用哈希表做字符统计
str1 -> 字符统计 -> hash1
str2 -> 字符统计 -> hash2
比对hash1与hash2的记录是否一致

其他方法

可以使用固定长度的数组来代理哈希表结构，时间复杂度为O(N)，额外空间复杂度为O(N)

代码实现

/**
 * 对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。
 * <p>
 * 给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。
 * <p>
 * 测试样例：
 * "abc",3,"bca",3
 * 返回：true
 *
 * @author NikoBelic
 * @create 2017/8/6 18:01
 */
public class ChkTransfrom
{
    public boolean chkTransform(String a, int lenA, String b, int lenB)
    {
        if (a.equals(b))
        {
            return true;
        }
        if (lenA != lenB)
        {
            return false;
        }
        Map<Character, Integer> hashA = new HashMap<>();
        Map<Character, Integer> hashB = new HashMap<>();
        for (char c : a.toCharArray())
        {
            hashA.put(c, hashA.get(c) == null ? 1 : hashA.get(c) + 1);
        }
        for (char c : b.toCharArray())
        {
            hashB.put(c, hashB.get(c) == null ? 1 : hashB.get(c) + 1);
        }
        for (Map.Entry<Character, Integer> entry : hashA.entrySet())
        {
            if (hashB.get(entry.getKey()) == entry.getValue())
                continue;
            return false;
        }
        return true;
    }
    public static void main(String[] args)
    {
        System.out.println(new ChkTransfrom().chkTransform("DAQT", 4, "QDAT", 4));
    }
}

例题3

最优解时间复杂度为O(N)
判断s1与s2是否长度相等
- 不等直接返回false
如果长度相等，生成s1+s1的大字符串
使用KMP算法判断大字符串中是否包含s2
- 如果包含则说明s1与s2互为旋转词

例题4

实现将字符串局部所有字符逆序的函数f
- 第i个字符和第n-i个字符交换顺序即可实现
利用f将字符串所有字符逆序
找到逆序后的字符串中每一个单词的区域，利用f将每一个单词区域逆序

/**
 * 对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。
 * <p>
 * 给定一个原字符串A和他的长度，请返回逆序后的字符串。
 * <p>
 * 测试样例：
 * "dog loves pig",13
 * 返回："pig loves dog"
 *
 * @author NikoBelic
 * @create 2017/8/6 20:44
 */
public class ReverseSentence
{
    public String reverseSentence(String a, int n)
    {
        String reversedStr = reverseChars(a.toCharArray());
        String reversedWords = "";
        for (String word : reversedStr.split(" "))
        {
            reversedWords += reverseChars(word.toCharArray());
            reversedWords += " ";
        }
        if (reversedWords.length() > 1)
        {
            return reversedWords.substring(0, reversedWords.length() - 1);
        }
        return reversedWords;
    }
    private String reverseChars(char[] chars)
    {
        char c;
        for (int i = 0; i < chars.length / 2; i++)
        {
            c = chars[i];
            chars[i] = chars[chars.length - i - 1];
            chars[chars.length - i - 1] = c;
        }
        return String.valueOf(chars);
    }
    public static void main(String[] args)
    {
        ReverseSentence reverseSentence = new ReverseSentence();
        String s = "Niko Belic Is A Good Boy.";
        System.out.println(reverseSentence.reverseSentence(s, s.length()));
    }
}

例题5

先将str[0,i]逆序
再将str[i+1,n-1]逆序
将整个str逆序

代码实现

public class StringTranslation
{
    public String stringTranslation(String a, int n, int len)
    {
        String reversedStr = reverseStr(a.toCharArray());
        return reverseStr(reversedStr.substring(0, n - len).toCharArray()) + reverseStr(reversedStr.substring(n - len).toCharArray());
    }
    private String reverseStr(char[] a)
    {
        char c;
        for (int i = 0; i < a.length / 2; i++)
        {
            c = a[i];
            a[i] = a[a.length - i - 1];
            a[a.length - i - 1] = c;
        }
        return String.valueOf(a);
    }
    public static void main(String[] args)
    {
        StringTranslation stringTranslation = new StringTranslation();
        String s = "ABCDE";
        System.out.println(stringTranslation.stringTranslation(s, s.length(), 3));
    }
}

例题6

最优时间复杂度O(N*logN)，其实质是一种排序的实现

代码实现

public String findSmallest(String[] strs, int n)
    {
        String tmp;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if ((strs[i] + strs[j]).compareTo(strs[j] + strs[i]) > 0)
                {
                    tmp = strs[i];
                    strs[i] = strs[j];
                    strs[j] = tmp;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (String str : strs)
        {
            sb.append(str);
        }
        return sb.toString();
    }

例题7

代码实现

public class Replacement
{
    public String repalceSpace(String iniString, int length)
    {
        if (iniString == null || iniString.equals(""))
            return "";
        int spaceCount = iniString.split(" ").length - 1;
        char[] initChars = iniString.toCharArray();
        char[] resChars = new char[iniString.length() + spaceCount * 2];
        int j = resChars.length - 1;
        for (int i = length - 1; i >= 0; i--)
        {
            if (initChars[i] != ' ')
            {
                resChars[j--] = initChars[i];
            } else
            {
                resChars[j--] = '0';
                resChars[j--] = '2';
                resChars[j--] = '%';
            }
        }
        return String.valueOf(resChars);
    }
    public static void main(String[] args)
    {
        Replacement r = new Replacement();
        String s = "Niko Belic Is A Good Boy";
        System.out.println(r.repalceSpace(s, s.length()));
    }
}

例题8

代码实现

public boolean chkParenthesis(String a, int n)
{
    int num = 0;
    for (char c : a.toCharArray())
    {
        if (c == '(')
        {
            num++;
        } else
        {
            num--;
        }
        if (num < 0)
        {
            return false;
        }
    }
    if (num == 0)
        return true;
    return false;
}

例题9

解法

代码实现

public class DistinctSubString
{
    public int longestSubstring(String A, int n)
    {
        char[] chas = A.toCharArray();
        int len = -1;
        int[] map = new int[255];
        int pre = -1;
        int cur = 0;
        Arrays.fill(map, -1);
        for (int i = 0; i < n; i++)
        {
            pre = Math.max(pre, map[chas[i]]);
            cur = i - pre; // ?
            len = Math.max(len, cur);
            map[chas[i]] = i;
        }
        return len;
    }
    public int l2(String A, int size)
    {
        int i, j;
        char[] str = A.toCharArray();
        int longest = 0;
        int[] visit = new int[255];
        for (i = 0; i < size; ++i)
        {
            Arrays.fill(visit, 0);
            visit[str[i]] = 1;
            for (j = i + 1; j < size; ++j)
            {
                if (visit[str[j]] == 0)
                {
                    visit[str[j]] = 1;
                } else
                {
                    if (j - i > longest)
                    {
                        longest = j - i;
                    }
                    break;
                }
            }
            if ((j == size) && (j - i > longest))
            {
                longest = j - i;
            }
        }
        return longest;
    }
    public static void main(String[] args)
    {
        DistinctSubString d = new DistinctSubString();
        //System.out.println(d.longestSubstring("ABCDA", 5));
        System.out.println(d.l2("spnvw", 5));
    }
}