美文网首页
算法(五)-字符串

算法(五)-字符串

作者: Stan_Z | 来源:发表于2020-01-09 23:40 被阅读0次
    1. 最长公共前缀

    示例 1:
    输入: ["flower","flow","flight"]
    输出: "fl"
    示例 2:
    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。
    说明:所有输入只包含小写字母 a-z 。

        public static String longestCommonPrefix(String[] strs) {
            if (strs.length == 0) {
                return "";
            }
            for (int i = 0; i < strs[0].length(); i++) {
                char c = strs[0].charAt(i);
                for (int j = 1; j < strs.length; j++) {
                    if (i == strs[j].length() || c != strs[j].charAt(i)) {
                        return strs[0].substring(0, i);
                    }
                }
            }
            return strs[0];
        }
    
    2. 字符串的排列

    给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
    换句话说,第一个字符串的排列之一是第二个字符串的子串。
    示例1:
    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba").
    示例2:
    输入: s1= "ab" s2 = "eidboaoo"
    输出: False
    注意:
    输入的字符串只包含小写字母
    两个字符串的长度都在 [1, 10,000] 之间

        public static boolean checkInclusion(String s1, String s2) {
            if (s1 == null || s1 == "" || s2 == null || s2 == "") {
                return false;
            }
    
            char[] c1 = s1.toCharArray();
            LinkedList<Integer> list = new LinkedList();
    
            //有一个字符不包含直接退出
            for (int i = 0; i < c1.length; i++) {
                String s = String.valueOf(c1[i]);
                if (!s2.contains(s)) {
                    return false;
                }
                list.add(s2.indexOf(s));
            }
    
            //证明字符都包含,那就看是不是挨在一起
            if (Math.abs(list.peekLast() - list.peekFirst()) == s1.length() - 1) {
                return true;
            }
            return false;
        }
    
    3. 无重复字符的最长子串

    示例 1:
    输入: "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
    示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
    示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
    请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

        public static int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
    
            int start = 0;
            String result;
            int max = 0;
            for (int i = 0; i < s.length(); i++) {
                result = s.substring(start, i + 1);
                if (result.length() > max) {
                    max = result.length();
                }
                if (i + 1 < s.length() && result.contains(String.valueOf(s.charAt(i + 1)))) {
                    result = String.valueOf(s.charAt(i + 1));
                    start = i + 1;
                }
            }
    
            return max;
        }
    

    未完待续....

    相关文章

      网友评论

          本文标题:算法(五)-字符串

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