LeetCode刷题之字符串

1221. 分割平衡字符串

在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。

示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。

示例 2：
输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。

题解：

class Solution {
        public int balancedStringSplit(String s) {
        String restStr = s;
        ArrayList<String> list = new ArrayList<>();
        while (restStr.length()>0) {
            restStr = getPinghengStr(restStr)[1];  //获取剩余字符串循环处理
            list.add(getPinghengStr(restStr)[0]);  //存储各个生成的平衡字符串
        }

        return list.size();
    }

    /**
     * 传入一个字符串，截取平衡字符串，同时返回剩余字符串
     * @param str
     * @return
     */
    private String[] getPinghengStr(String str) {
        String jugeStr;
        for (int i=1;i<str.length();i++) {
            jugeStr = str.substring(0, i);

            //判断R和L出现的次数是否相等
            int rCount = 0; //R出现的次数
            int lCount = 0; //L出现的次数
            for (int j=0;j<jugeStr.length();j++) {
                if (jugeStr.charAt(j) == 'R') {
                    rCount++;
                } else if (jugeStr.charAt(j) == 'L') {
                    lCount++;
                }
            }
            if (rCount == lCount) {
                //判断是平衡字符串，返回结果
                return new String[]{jugeStr, str.substring(i)};
            } else {
                //继续循环加长字符判断
                continue;
            }
        }

        return new String[]{"", ""};
    }
}

1436. 旅行终点站

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

示例 1：
输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo"
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：
输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
显然，旅行终点站是 "A" 。

题解：

class Solution {

    public String destCity(List<List<String>> paths) {
        //思路，将每一个地点存入map中，出现一次值+1，所以整个路径的起点和终点次数是1，途径地点次数为2，最后返回终点
        //区分起点和终点：给键字符串加一个< >符号， <表示起点, >表示结束点
        //用另一个map存每个字符串添加时是起点还是终点的标识
        Map<String,Integer> record = new HashMap<>();
        Map<String, Integer> startEnd = new HashMap<>();
        List<String> curPath;

        for (int i=0;i<paths.size();i++) {
            curPath = paths.get(i);

            for (int j=0;j<curPath.size();j++) {
                //字符串次数+1
                if (!record.containsKey(curPath.get(j))) {
                    record.put(curPath.get(j), 1);

                    startEnd.put(curPath.get(j), j%2);  //是起点，存0，是结束点，存1
                } else {
                    record.put(curPath.get(j), record.get(curPath.get(j)) + 1);
                }
            }
        }

        Set<Map.Entry<String, Integer>> entries = record.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            if (entry.getValue() == 1 && startEnd.get(entry.getKey()) == 1) {
                //出现一次的结束点即为旅行的终点
                return entry.getKey();
            }
        }

        return "";
    }

}

709. 转换成小写字母

实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

示例 1：
输入: "Hello"
输出: "hello"

示例 2：
输入: "here"
输出: "here"

题解：

class Solution {
    public String toLowerCase(String str) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i=0;i<str.length();i++) {
            if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {
                stringBuilder.append(upToLow(str.charAt(i)));  //大写字母先转小写，再添加
            } else {
                stringBuilder.append(str.charAt(i));  //小写字母直接添加
            }
        }
        return stringBuilder.toString();
    }

    /**
     * 大写字母转小写
     * @param c
     * @return
     */
    public char upToLow(char c) {
        if (c >= 'A' && c <= 'Z') {
            //判断c为大写字母
            c += 32;
        }
        return c;
    }
}

804. 唯一摩尔斯密码词

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串，比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。

为了方便，所有26个英文字母对应摩尔斯密码表如下：

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + ".-" + "-..." 字符串的结合)。我们将这样一个连接过程称作单词翻译。

返回我们可以获得所有词不同单词翻译的数量。

例如:
输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释:
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
共有 2 种不同翻译, "--...-." 和 "--...--.".

题解：

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        //思路：将字符串数组每个字符串，去每个字符对应表里获取该字符串的摩斯码串，
        //将各个摩斯码字符串存入set中去重，set的长度就是不同单词的数量

        String[] morseCodeTable = new String[]{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        Set<String> codes = new HashSet<>();
        for (String word : words) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i=0;i<word.length();i++) {
                String psd = morseCodeTable[word.charAt(i)-'a'];
                stringBuilder.append(psd);  //当前字符在摩尔斯码表中的符号
            }
            codes.add(stringBuilder.toString());
        }

        return codes.size();
    }
}

557. 反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

题解：

class Solution {
    public String reverseWords(String s) {
        String[] subStrArray = s.split(" ");
        //将每一个子字符串倒转
        StringBuilder stringBuilder = new StringBuilder();
        for (int i=0;i<subStrArray.length;i++) {
            stringBuilder.delete(0, stringBuilder.length()-1);  //清楚数据重复使用
            subStrArray[i] = stringBuilder.append(subStrArray[i]).reverse().toString();
        }

        for (int i=0;i<subStrArray.length;i++) {
            stringBuilder.append(subStrArray[i] + " ");
        }

        return stringBuilder.deleteCharAt(stringBuilder.length()-1).toString();
    }
}

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

题解：

class Solution {
    public void reverseString(char[] s) {
        //原地倒转字符数组，采用对应位置交换值的方法
        int start = 0;
        int end = s.length-1;
        //要交换的次数
        char temp;
        while (start < end) {
            temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            //位置往中间靠
            start++;
            end--;
        }

    }
}

面试题 01.02. 判定是否互为字符重排

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：
输入: s1 = "abc", s2 = "bca"
输出: true

示例 2：
输入: s1 = "abc", s2 = "bad"
输出: false

题解：

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        //思路：遍历s1中每一个字符，从s2中从左到右依次找这个字符，找到就将该字符从s2中删去，然后遍历下一个字符，直到遍历完
        //如果中途出现找不到的字符，说明不能变成另一个字符串。

        //首先：第一步，s1和s2长度需要相等
        if (s1.length() != s2.length()) {
            return false;
        }

        String temp = s2;
        for (int i=0;i<s1.length();i++) {
            int pos = temp.indexOf(s1.charAt(i));  //找到这个字符的下标，将其从s2中删除，找不到返回-1
            if (pos == -1) {
                return false;
            } else {
                temp = strRemoveChar(temp, pos);
            }
        }
        return true;
    }

        /**
     * 删除字符串指定位置的字符
     * @param string
     * @param pos
     * @return
     */
    public String strRemoveChar(String string, int pos) {
        return string.substring(0, pos) + string.substring(pos+1);
    }

}

1189. “气球” 的最大数量

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。

字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。

示例 1：
输入：text = "nlaebolko"
输出：1

示例 2：
输入：text = "loonbalxballpoon"
输出：2

示例 3：
输入：text = "leetcode"
输出：0

题解：

class Solution {
    public int maxNumberOfBalloons(String text) {
        //思路：遍历balloon单词每个字符，从text中找这个字符，找到一个就删除，继续下一个字符。
        //一个balloon单词找完，就循环找下一个单词，知道从text中找不到某个字符，获取当前找到的完整balloon个数

        String wordBalloon = "balloon";
        String tempText = text;
        int spellCount = 0;  //拼出完整balloon单词的次数
        while (true) {
            for (int i=0;i<wordBalloon.length();i++) {
                char curChar = wordBalloon.charAt(i);
                int pos = tempText.indexOf(curChar);
                if (pos == -1) {
                    //没有找到该字符
                    return spellCount;
                } else {
                    tempText = strRemoveChar(tempText, pos);
                }
            }

            //一个单词循环完毕，单词量+1
            spellCount++;
        }
    }

        /**
     * 删除字符串指定位置的字符
     * @param string
     * @param pos
     * @return
     */
    public String strRemoveChar(String string, int pos) {
        return string.substring(0, pos) + string.substring(pos+1);
    }
}

1408. 数组中的字符串匹配

给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按任意顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。

示例 1：
输入：words = ["mass","as","hero","superhero"]
输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。

示例 2：
输入：words = ["leetcode","et","code"]
输出：["et","code"]
解释："et" 和 "code" 都是 "leetcode" 的子字符串。

示例 3：
输入：words = ["blue","green","bu"]
输出：[]

题解：

class Solution {
    public List<String> stringMatching(String[] words) {
        //思路：遍历words数组，若其它字符串包含该字符串，则这个字符串为子串输出

        Set<String> subStr = new HashSet<>();  //记录子字符串，注意这个坑，不能记录重复，所以用set来存一遍
        for (int i=0;i<words.length;i++) {
            String curWord = words[i];

            for (int j=0;j<words.length;j++) {
                if (!words[j].equals(curWord) && words[j].contains(curWord)) {
                    subStr.add(curWord);
                }
            }
        }

        return new ArrayList<>(subStr);
    }
}

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

题解：

class Solution {
    public int strStr(String haystack, String needle) {
        int needleLength = needle.length();
        if (!haystack.contains(needle)) {
            //不包含，直接返回-1
            return -1;
        } else {
            //包含
            for (int i=0;i<=haystack.length()-needleLength;i++) {
                String compareStr = haystack.substring(i, i+needleLength);
                if (needle.equals(compareStr)) {
                    return i;
                }
            }
            return -1;
        }
    }
}

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

题解：

class Solution {
    /**
     * 最长公共前缀
     *
     * 思路：取出最短的一个字符串，将里面依次字符取出，和其他字符比较
     * 相同，则添加到公共字符串里，如果不相同，则返回当前公共字符串
     */
    public static String longestCommonPrefix(String[] strs) {
         if (strs.length == 1) {
            return strs[0];
        }
        StringBuilder stringBuilder = new StringBuilder();
        int shortestStrLeng = strs[0].length();
        int shortestStrPos = 0;
        for (int i=0;i<strs.length;i++) {
            if (strs[i].length() == 0) {
                return "";
            }
            if (strs[i].length() < shortestStrLeng) {
                shortestStrLeng = strs[i].length();
                shortestStrPos = i;
            }
        }

        for (int i=0;i<strs[shortestStrPos].length();i++) {
            ///将所有字符串的依次i个位置字符拿来比较是否相同
            char cr = strs[shortestStrPos].charAt(i);
            for (int j=0;j<strs.length;j++) {
                if (cr != strs[j].charAt(i)) {
                    return stringBuilder.toString();
                }
            }
            stringBuilder.append(cr);
        }
        return stringBuilder.toString();
    }
}