Очередная задачка уровня Easy, но с довольно низким показателем Acceptance (44.4%). Что выражается в достаточно обширном наборе граничных случаев, некоторые из которых делают больно 🙂

Было желание сделать за один проход по исходной строке (без выделения дополнительно памяти). Вроде даже получилось, если ориентироваться на статистику запуска с LeetCode.

class Solution {

    private static final int LETTER_CASE_SHIFT = 32;

    public boolean isPalindrome(String s) {
        if (s.length() == 1) return true;
        char a, b;
        int mid = (s.length() - 1) >>> 1;
        for (int i = 0, j = s.length() - 1; i <= mid; i++, j--) {
            a = s.charAt(i);
            b = s.charAt(j);
            while (isNotAlphaNumeric(a) && i < j) {
                a = s.charAt(++i);
            }
            while (isNotAlphaNumeric(b) && i < j) {
                b = s.charAt(--j);
            }
            if (isComparable(a, b)) {
                if (!equalsIgnoreCase(a, b)) {
                    return false;
                }
            } else {
                return false;
            }
            mid = (i + j) / 2;
        }
        return true;
    }

    private static boolean equalsIgnoreCase(char a, char b) {
        return a == b
            || a - LETTER_CASE_SHIFT == b
            || a == b - LETTER_CASE_SHIFT;
    }

    private static boolean isComparable(char a, char b) {
        return (isLetter(a) && isLetter(b))
            || (!isLetter(a) && !isLetter(b));
    }

    private static boolean isLetter(char ch) {
        return 'a' <= ch && ch <= 'z'
            || 'A' <= ch && ch <= 'Z';
    }

    private static boolean isNotAlphaNumeric(char ch) {
        return !isLetter(ch) && ('0' > ch || ch > '9');
    }

}

Success:
    Runtime:2 ms, faster than 99.92% of Java online submissions.
    Memory Usage:42.3 MB, less than 87.41% of Java online submissions.

Ссылка на решение на Гитхаб.

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.

https://leetcode.com/problems/valid-palindrome/

Ещё одна простая задачка – определение процентного содержания целевого символа в исходной строке. Пара решений:

• через стримы (примитивно, без кастомной свёртки, да и помедленней)
• и через цикл for.

Стримы

public int percentageLetter(String s, char letter) {
    long cnt = s.chars().filter(it -> it == (int) letter).count();
    return (int) (100 * cnt / s.length());
}

Success:
    Runtime:2 ms, faster than 12.22% of Java online submissions.
    Memory Usage:40.6 MB, less than 45.95% of Java online submissions.

Цикл

public int percentageLetter(String s, char letter) {
    int cnt = 0;
    for (char c : s.toCharArray()) {
        cnt += c == letter ? 1 : 0;
    }
    return 100 * cnt / s.length();
}

Success:
    Runtime:0 ms, faster than 100.00% of Java online submissions.
    Memory Usage:40.1 MB, less than 88.72% of Java online submissions.

Решение на гитхабе.

Given a string s and a character letter, return the percentage of characters in s that equal letter rounded down to the nearest whole percent.

https://leetcode.com/problems/percentage-of-letter-in-string/

Тоже забавная задачка – со “сломанной клавиатурой”. Решил в ней Arrays.binarySearch использовать для поиска буквы слова в наборе “сломанных клавишей”, да и чтобы не забыть о его (метода) существовании в целом.

Судя по статистике – нормально получилось, в общем-то.

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        var brL = brokenLetters.toCharArray();
        Arrays.sort(brL);
        var words = text.split(" ");
        int canTypeCnt = 0;
        for (var word : words) {
            boolean canType = true;
            for (int i = 0; i < word.length(); i++) {
                if (Arrays.binarySearch(brL, word.charAt(i)) >= 0) {
                    canType = false;
                    break;
                }
            }
            if (canType) {
                canTypeCnt++;
            }
        }
        return canTypeCnt;
    }
}

Success:
	Runtime:2 ms, faster than 91.93% of Java online submissions.
	Memory Usage:42.7 MB, less than 23.23% of Java online submissions.

То же решение на гитхабе.

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

https://leetcode.com/problems/maximum-number-of-words-you-can-type/

Приятная задачка выпала в поиске – хоть и easy, а сделать интересно. Какая-то “практическая применимость” в ней видится.

Вроде, там где-то и обратная проблема была – перевод записи арабскими цифрами в запись римскими.

В общем-то, список валидных префиксов там прямо в условии задачи описан, особо выдумывать тут ничего не требуется.

class Solution {
    private Map<Character, Integer> values = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
    private Map<Character, Set<Character>> prefixes = Map.of('I', Set.of('V', 'X'), 'X', Set.of('L', 'C'), 'C', Set.of('D', 'M'));

    public int romanToInt(String s) {
        int max = s.length() - 1;
        int sum = 0;
        int i = 0;
        while (i <= max) {
            char c = s.charAt(i);
            if (prefixes.containsKey(c) && i < max && prefixes.get(c).contains(s.charAt(i + 1))) {
                sum += values.get(s.charAt(++i)) - values.get(c);
            } else {
                sum += values.get(c);
            }
            i++;
        }
        return sum;
    }
}

Читать далее LeetCode 13. Roman to Integer →