字符串相关算法

目录

• 3.无重复字符的最长子串
• 125. 验证回文串
• 20.有效括号
• 344.反转字符串
• 557.反转字符串中的单词 III
• 567. 字符串的排列

题目

3. 无重复字符的最长子串

滑动窗口

    /**
     *  从头到尾遍历字符串，如果List集合中不包含遍历到的字符 c ，则将字符串 c 放入 List 集合中，
     *  如果包含遍历到的字符串，那么这个结合中的 size 可能就是最大值，与 maxSize 对比，将最大值保存到
     *  maxSize,然后从集合头部开始移除元素，直到集合中不包含遍历到的这个字符 c 为止,然后将字符串 c 存入集合中。
     *  字符串遍历结束后 maxSize 与 List size 的最大值即为最大字符串。
     */
    public static int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        List<Character> list = new ArrayList<>();
        int maxSize = 0;
        for (Character c : chars) {
            if (list.size() < chars.length) {
                if (list.contains(c)) {
                    maxSize = Math.max(list.size(), maxSize);
                    while (list.size() > 0 && list.contains(c)) {
                        list.remove(0);
                    }
                }
                list.add(c);
            }
        }

        return Math.max(maxSize, list.size());
    }

125. 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串 示例 2:

输入: "race a car" 输出: false 解释："raceacar" 不是回文串

提示：

1 <= s.length <= 2 * 105 字符串 s 由 ASCII 字符组成

解题思路

 public static boolean isPalindrome(String s) {
    int right = s.length() - 1;
    int left = 0;
    while (left < right) {
      char leftChar = s.charAt(left);
      while (!Character.isLetterOrDigit(leftChar) && left < right) {
        leftChar = s.charAt(++left);
      }
      char rightChar = s.charAt(right);
      while (!Character.isLetterOrDigit(rightChar) && left < right) {
        rightChar = s.charAt(--right);
      }
      if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()" 输出：true 示例 2：

输入：s = "()[]{}" 输出：true 示例 3：

输入：s = "(]" 输出：false 示例 4：

输入：s = "([)]" 输出：false 示例 5：

输入：s = "{[]}" 输出：true

提示：

1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成

解题思路

public boolean isValid(String s) {
    int length = s.length();
    if (length % 2 == 1) {
        return false;
    }
    HashMap<Character, Character> pairs = new HashMap<>() {
        {
            put('(', ')');
            put('[', ']');
            put('{', '}');
        }
    };
    LinkedList<Character> stack = new LinkedList<>();

    for (int i = 0; i < length; i++) {
        char c = s.charAt(i);
        if (pairs.get(c) == null) {
            if (stack.size() > 0) {
                Character pop = stack.pop();
                if (c != pairs.get(pop)) {
                    return false;
                }
            } else {
                return false;
            }

        } else {
            stack.push(c);
        }
    }
    return stack.size() == 0;
}

344. 反转字符串

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

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

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

示例 1：

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

输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

解题思路

通过双指针方式实现，第一个指针指向数组头，第二个指针指向数组尾，交换指针出的元素，然后左指针+1，右指针-1.直到左指针大于等于右指针停止。

public void reverseString(char[] s) {
    int p1 = 0, p2 = s.length - 1;
    while (p1 < p2) {
        swap(s, p1, p2);
        p1++;
        p2--;
    }
}

public void swap(char[] c, int p1, int p2) {
    char temp = c[p1];
    c[p1] = c[p2];
    c[p2] = temp;
}

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

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

示例：

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

提示：

在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

解题思路

public String reverseWords(String s) {
    char[] chars = s.toCharArray();
    int p1 = 0, p2 = 0, index = 0;
    for (int i = 0; i < chars.length; i++) {
        if (chars[index] == ' ' || i == chars.length - 1) {
            p2 = index;
            reverseWord(chars, p1, p2);
            p1 = index + 2;
        }
        index++;
    }

    return new String(chars);
}

private void reverseWord(char[] chars, int p1, int p2) {
    while (p1 < p2) {
        char temp = chars[p1];
        chars[p1] = chars[p2];
        chars[p2] = temp;
        p1++;
        p2--;
    }
}

567. 字符串的排列

    /**
     * s1是较短的字符串，如果s1的排列是s2的字串，那么s1中各个字符的个数与s2
     * 某个字串各个字符串的个数是相等的，则条件成立。因此可以申请两个长度为26的数组
     * 第一个数组统计s1中各个字符串的个数，第二个数组统计s2长度为s1.length的字串的各个字符个数。
     * 如果s2中存在条件成立的字串，那么两个数组是相等的。
     */
    public static boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int[] ints1 = new int[26];
        int[] ints2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            ++ints1[s1.charAt(i) - 'a'];
            ++ints2[s2.charAt(i) - 'a'];
        }
        if (Arrays.equals(ints1, ints2)) {
            return true;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            ++ints2[s2.charAt(i) - 'a'];
            --ints2[s2.charAt(i - s1.length()) - 'a'];
            if (Arrays.equals(ints1, ints2)) {
                return true;
            }
        }
        return false;
    }