5. Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路:参考某位大神的解题思路,找到最长的palindromic子串,找palindrome的时候可以从某个点坐标i 按照偶数展开(i-1, i+1), 或者按照奇数展开(i,i+1)。 找palindrome的方法可以两个指针挨个比较。因为需要找最长的palindrome子串,可以用一个全局的maxLen变量每次找到子串后进行比较,并把较长的那个赋给最后结果。

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        String maxRes = ""; 
        int maxLen = 0;
        // even expand
        for (int i = 0; i < s.length(); i++) {
            String tmp = expand(s, i - 1, i + 1);
            if (maxLen < tmp.length()) {
                maxLen = tmp.length();
                maxRes = tmp;
            }

        }
        // odd expand
        for (int i = 0; i < s.length(); i++) {
            String tmp = expand(s, i, i + 1);
            if (maxLen < tmp.length()) {
                maxLen = tmp.length();
                maxRes = tmp;
            }

        }
        return maxRes;
    }

    public String expand(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}
Advertisements

387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.
思路: 本题找第一次出现的非重复的字符的坐标, 首先我们需要把坐标给保存起来,还得把重复出现的字符给去掉,然后再从保存的坐标中找到最小的,即第一次出现的非重复坐标的位置。
我们可以用一个map来保存每个字母的坐标,如果字母重复出现,坐标就置为-1. 最后从map中找到value不为-1的最小值。

public class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) return -1;
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            Character letter = s.charAt(i);
            if (map.containsKey(letter)) {
                map.put(letter, -1);
            } else {
                map.put(letter, i);
            }
        }
        int min = s.length(); // find the min pos
        for(Map.Entry<Character, Integer> entry: map.entrySet() ) {
            if (entry.getValue() != -1) {
                if (min > entry.getValue()) {
                    min = entry.getValue();
                }
            }
        }
        return min == s.length() ? -1 : min;

    }
}