242 valid letter heterotopic words

Title description:

Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S. That is, to determine whether two strings contain exactly the same characters.

Example:

Enter: s ="anagram", t = "nagaram"Output:trueEnter: s ="rat", t = "car"Output:false
Copy the code

Note: You can assume that strings contain only lowercase letters.

Answer key:

  • Check whether the two strings are equal in length. If they are not equal, return false.
  • And then we have a new oneHashMap<Character,Integer>, used to store characters and the corresponding times;
  • Put string S into map, and record the number of characters appearing CNT;
  • Iterates over characters in string t, if map does not exist, return false;
  • If yes, check whether the corresponding CNT is greater than 0. If yes, the corresponding CNT is CNT-1; if no, return false.
  • If CNT <0, return false;
  • The end.

Code:

import java.util.HashMap;
import java.util.Map;

/* * @lc app=leetcode.cn id=242 lang= Java * * [242] Valid letter heterotopic */

// @lc code=start
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() ! = t.length()) {return false;
        }
        //new hashmap
        Map<Character,Integer> sMap = new HashMap<>();
	   // Iterate over the s string
        for (char c : s.toCharArray()) {
            sMap.put(c, sMap.getOrDefault(c, 0) + 1);
        } 
        /* for (char c : t.toCharArray()) { sMap.put(c, sMap.getOrDefault(c, 0) - 1); if (sMap.get(c) < 0) { return false; }} * /
	   // Iterate over the t string
        for (char c : t.toCharArray()) {
            if (sMap.containsKey(c) && sMap.get(c) > 0) {
                sMap.put(c, sMap.get(c) - 1);
            }else{
                return false; }}return true; }}// @lc code=end
Copy the code

205 Isomorphic character string

Title description:

Given two strings s and t, determine whether they are isomorphic.

If the characters in S can be replaced by some mapping to give t, then the two strings are isomorphic.

Each occurrence of a character should map to another character without changing the order of the characters. Different characters cannot be mapped to the same character. The same character can only be mapped to the same character. Characters can be mapped to themselves.

Example:

Enter: s ="egg", t = "add"Output:trueEnter: s ="foo", t = "bar"Output:falseEnter: s ="paper", t = "title"Output:true
Copy the code

We can assume that s and t have the same length.

Answer key:

We judge whether the characters at each position of S and T have a one-to-one correspondence, that is, any character of S corresponds to a unique character in T, and any character of T corresponds to a unique character in S. This is also known as a “bijective” relationship.

For example, s = “foo”, t = “bar”, although characters A and r in T have a unique mapping O, there are two mappings {a,r} for character O in S, so the condition is not satisfied.

Therefore, we maintain two hash tables, the first hash table S2T with characters in S as keys and characters mapped to T as values, and the second hash table T2s with characters in T as keys and characters mapped to S as values. Iterating through two strings of characters from left to right, updating two hash tables continuously, If a conflict occurs (that is, the character S [index] corresponding to the current index has been mapped and is not T [index], or the character T [index] corresponding to the current index has been mapped and is not S [index]), the two strings cannot form isomorphism. Returns false.

If there is no conflict at the end of the traversal, the two strings are isomorphic and return true.

Code:

import java.util.HashMap;
import java.util.Map;

/* * @lc app=leetcode.cn id=205 lang= Java * * [205] Ishomogeneous string */

// @lc code=start
class Solution {
    public boolean isIsomorphic(String s, String t) {
        // Define two hash tables
        Map<Character,Character> s2t = new HashMap<>();
        Map<Character,Character> t2s = new HashMap<>();

        int size = s.length();
        // Iterate over the string
        for (int i = 0; i < size; i++) {
            char a = s.charAt(i);/ / s characters
            char b = t.charAt(i);/ / t characters
            // s[I] is already mapped to t[I]
            if(s2t.containsKey(a) && s2t.get(a) ! = b) {return false;
            }
            // t[I] is already mapped and not s[I]
            if(t2s.containsKey(b) && t2s.get(b) ! =a ) {return false;
            }
            s2t.put(a, b);
            t2s.put(b, a);
        }
        
        return true; }}// @lc code=end
Copy the code

647 text substring

Title description:

Given a string, your task is to calculate how many substrings are in the string.

Substrings with different starting or ending positions are treated as different substrings, even if they are composed of the same characters.

Example:

Input:"abc"Output:3Explanation: three anagram substrings:"a"."b"."c"Input:"aaa"Output:6Explanation:6A string of subscripts:"a"."a"."a"."aa"."aa"."aaa"
Copy the code

Answer key:

Take one or two adjacent characters in the string as the center, and then expand left and right respectively through two Pointers, and record whether the current moment has palindrome attribute in the process of expansion.

Code:

/* * @lc app=leetcode.cn id=647 lang= Java * * [647] loopback string */

// @lc code=start
class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += extendSubstrings(s, i, i);/ / even
            count += extendSubstrings(s, i, i+1);/ / odd
        }
        return count;
    }
    public static int extendSubstrings(String s,int left,int right){
        int count = 0;
        while (left >= 0 && right <s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
            ++count;
        }
        returncount; }}// @lc code=end
Copy the code

696 counts binary substrings

Title description:

Given a string s, count the number of non-empty (continuous) substrings that have the same number of zeros and ones, and all zeros and all ones in those substrings are combined.

Repeated substrings count the number of times they occur.

Example:

Input:"00110011"Output:6Explanation:6Substrings have the same number of continuities1and0:"0011","01","1100","10","0011"And"01". Note that some repeated substrings count their occurrences. In addition,"00110011"Is not a valid substring because all0(and1) Not put together. Input:"10101"Output:4Explanation:4Substring:"10","01","10","01", they have the same amount of continuity1and0.Copy the code

Answer key:

  1. Official solution:

    We can group the string s by 0 and 1 segments. For example, s=00111011. We get counts={2,3,1,2}.

    The two adjacent numbers in the COUNTS array must represent two different characters. Suppose the two adjacent numbers in the COUNTS array are u or V. They correspond to u zeros and V ones, or U ones and V zeros. The number of substrings they can form that satisfy the condition is min{u,v}, that is, the contribution of a pair of adjacent numbers to the answer.

    We can just go through all the neighboring pairs, sum up their contributions, and get the answer.

  2. Similar to the substring solution:

Code:

  1. Official solution code:

    class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> counts = new ArrayList<Integer>();
        int ptr = 0, n = s.length();
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            counts.add(count);
        }
        int ans = 0;
        for (int i = 1; i < counts.size(); ++i) {
            ans += Math.min(counts.get(i), counts.get(i - 1));
        }
        returnans; }}Copy the code

  2. Similar palindrome solution

    class Solution {
    public int countBinarySubstrings(String s) {
        int result = 0;
        char[] chars = s.toCharArray();
        for(int i = 1; i < s.length(); i++){
            int left = i - 1, right = i;
            char leftChar = chars[left];
            char rightChar = chars[right];
            if(leftChar == rightChar)
                continue;
            while(left >= 0&& right < s.length() && chars[left] == leftChar && chars[right] == rightChar){ left--; right++; result++; }}returnresult; }}Copy the code