String 算法思考

String 类型的题目算是leetcode里第二多的题型，其实这个和array的使用方法差不太多，只不过其中有一些特定的使用场景。我在这里会将string分为几类问题，可能不能包括所有的类别，尽量使用较为统一的思路解释遇到的题目。

数据类型

首先要说清楚一点，在java中String是immutable的，也就是当你创建一个string后是不能修改的，如果你需要给他加内容，java会重新创一个新的实例。这样的问题就是如果使用s+=a,这样时间复杂度是O(n),在java中会重新复制一遍string再给你创建。

解决办法就是使用StringBuilder，这个的时间复杂度对于增加就是O(1).其中内部实现就是一个char[]

  • sb.append(String str)
  • sb.toString()

组合问题

这类问题就是需要得到某个字符串中包含的所有子集,或者是permutation.这类题日非常相似，需要找出符合条件的所有组合。基本思路是样的，可以使用DFS与backtrack实现。例如 Combination Sum,可以把这题变成一个子问题选择了数字n后，求解sum-n的子问题的解答。所以可以先排序选择第一个元素，然后在函数中记录以下这些：

  • 结果列表
  • 当前路径存入的值，
  • 所有可能的值
  • 剩余的Sum
  • 当前选择的位置,深度

在执行递归前将数字存入，在执行后从数组中删去。如果是计算permutation, 在参种增加一个数组用来判断当前数字是否访过。类似的题目有以下这些：

对于subset的题目，可以用以下的思路.原因是只有这样才可能遍历所有的，第一dfs可以一直到底，之后再一个个增加。

dfs(){
    if(index ==length){
        rs.add(tmp);
        return;
    }
    dfs(index+1,tmp);
    newtmp = new ArrayList<>(tmp);
    newtmp.add(arr[index]);
    dfs(index+1,tmp);
}

一个注意点是：如果是用list的话，当加入结果的时候，每次需要重新构造一个新的： rs.add(new ArrayList<>(cur));

如果题目中存在重复的数字该如何处理呢？首先需要sort，然后就可以在遍历的时候首先看是不是前面两个一致，如果一致的话如果前面的没visited过就跳过。例如1,1,2, 第一个1遍历完了之后，第二个1就不需要作为首位了，所以这时就可以跳过第二个1作为首位的遍历。对于Palindrome的要求可以选定好中间，然后再从两边扩展。

还有一类题目就是和数学搭配，比如使用列表中的数计算24，可以使用各类运算.基本的思路是相似的，需要我们穷举所有可能的组合，唯一需要注意的就是乘法和除法，需要记录上一个数值的结果，把乘法的结果看作一个整体，一起计算。而算24点的话，首先选两个数，然后进行四则运算，把结果和剩下的数（3个）放到一个数组里，之后就可以递归对这3个数算24点。

括号问题

这也是string类的题目中一大类型，题目有判断是否是valid，可以使用stack的思想，只要是出现"(“之后的反方向括号一定是”)"。生成所有括号的思路和上面的dfs差不多，有两个参数记录剩下的括号数量，同时保证左括号比右括号少就可以了。

找出最长合理括号则可以使用DP来解决，可以把这个问题分成两大类：

  • ()()
  • (())
if(s.charAt(i) == ')') {
    if(s.charAt(i - 1) == '(') {
        dp[i] = 2 + (i >= 2 ? dp[i-2] : 0);
    } 
    // s.charAt(i - 1) == )
    else if(i - dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '(') { 
        dp[i] = 2 + dp[i-1] + ((i - dp[i-1]) >= 2 ? dp[i-dp[i-1]-2] : 0);
    }
    max = Math.max(max, dp[i]);
}

在数字中加括号的题目则是分治算法的典型代表，可以将所有的运算符的地方作为分界点，然后分别计算左右两边所有可能的值，之后再合并，得到最后所有的答案。括号是一个将数学表达式分开最合适的方法。

301题最简单的思路就是尝试所有的可能性，当出现不合理的情况时就直接舍弃。在尝试的时候测试使用括号和不使用括号两种可能性。

if (c == '(') {
        dfs(s, i + 1, res, sb, rmL - 1, rmR, open);		    // not use (
    	dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1);       // use (

    } else if (c == ')') {
        dfs(s, i + 1, res, sb, rmL, rmR - 1, open);	            // not use  )
    	dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1);  	    // use )

    } else {
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);	
    }

对于678，则可以使用贪心的思想，计算最小开放的括号以及最多开放的括号，如果不等于")“的个数小于”)“的话，那么就不可能是合理的。思路想清楚了不难，出现*这种就思考最多和最少的情况。

总体来说，stack的题目比较经典，因为这个模型非常简单易懂，也容易和其他的东西结合起来。

transform

这类题目指的是如何将一类的string改成其他的，比如罗马数字，英文,数字等等。这类题目就是看你的细心程度，根据规则一步一步推即可得到正确的答案。这类题目的难点一般在于有很多奇怪的输入需要思考，要不然很容易系统出错。

大部分都比较easy，比较有意思的就是find and replace 那道题，因为可能输入是没有序的，所以可以先用一个数组存在下需要match的index，然后再换就可以避免无序的问题。

Substring

这类题目一般就是双指针，以及使用一个数组记录所有出现过的值，比较要求。比如说第三题，要求求出最长没有重复字符的题目，我们可以用一个数组记录出现的字符，如果出现重复了，那么起始位置就增加，直到到上次出现的这个字符。

判断是否重复的题目只需要取可以整除长度的内容的substring，然后重复几遍，然后比较是否一致即可。对于回文数就是确定中心，往两边扫这种简单的思路。中心可能是一个字符也有可能是两个相同的字符。还有的题目只需一步一步来就好。

Trie

Trie是一种特别的数据类型，主要是使用一个树来代表string的前缀。一般的构造如下：

static class TrieNode
    {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
      
        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;
         
        TrieNode(){
            isEndOfWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };

在插入的时候，只需要在数组里新建下一个的TreeNode.在string的搜索上很有帮助。在每个节点都有一个变量来判断是不是一个单词的结束。

TODO:

Compare

还有一些题目就是需要来比较一些单词的，相似程度，比如说比较两个单词的距离，以及用一些东西来匹配这些字符串等。判断修改距离的题目。我们可以分成增加，删除以及修改三个层面进行讨论。判断那个字符之后其他字符的情况。而判断匹配的题目则可以使用动态规划的思路来做。也分成几个情况，一是完全匹配，还有就是匹配零个，三是匹配多个。

这类题目不是很好归纳，总之在比较字符串的时候需要用equals

模糊匹配的题目可以用一个map存这个单词最基本的情况，比如所有可以改变都变成a，新来的单词也把所有可以改变的变成a就可以了。

other