This is the third day of my participation in Gwen Challenge

This article is participating in “Java Theme Month – Java Development in Action”, see the activity link for details

I am Chen PI, an ITer of Internet Coding. I search “Chen PI’s JavaLib” on wechat and read the latest articles as soon as possible, reply to [information], and then I can get the technical materials, electronic books, interview materials of first-line big factories and excellent resume templates carefully arranged by me.

The title

Implement an algorithm that determines whether all characters of a string s are different.

Example 1:

  • Enter: s = “leetcode”
  • Output: false

Example 2:

  • Input: s = “ABC”
  • Output: true,

limit

  • 0 <= len(s) <= 100
  • Bonus points if you don’t use extra data structures.

LeetCode

Method a

To determine whether all characters in a string are unique, the simplest violent solution is whether the comparison of two characters is the same, that is, double loop, but the algorithm complexity is O(n^2), and the performance is the lowest. If the length of the string is relatively small, this algorithm can be used reluctantly.

package com.chenpi;

/ * * *@DescriptionImplement an algorithm that determines whether all characters of a string s are different. *@Author Mr.nobody
 * @Date 2021/4/18
 * @Version1.0 * /
public class StrIsUnique {

    public boolean isUnique(String astr) {
        // If the string is null or empty, there are no duplicate characters
        if (null == astr || 0 == astr.length()) {
            return true;
        }
        // Double loop
        for (int i = 0; i < astr.length() - 1; i++) {
            for (int j = i + 1; j < astr.length(); j++) {
                if (astr.charAt(i) == astr.charAt(j)) {
                    return false; }}}return true;
    }

    public static void main(String[] args) {
        String astr = "leetcode";
        StrIsUnique strIsUnique = newStrIsUnique(); System.out.println(strIsUnique.isUnique(astr)); }}Copy the code

Method 2

Since we are trying to determine uniqueness, we can go through each character, and then put them in the specified place by some rule, because the same character must be put in the same place, we just need to determine if there were any characters put in this place before, if there are, it means there are duplicate characters. This can be achieved with data structures such as hash tables.

package com.chenpi;

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

/ * * *@DescriptionImplement an algorithm that determines whether all characters of a string s are different. *@Author Mr.nobody
 * @Date 2021/4/18
 * @Version1.0 * /
public class StrIsUnique {

    public boolean isUnique(String astr) {
        // If the string is null or empty, there are no duplicate characters
        if (null == astr || 0 == astr.length()) {
            return true;
        }
        Map<Character, Integer> map = new HashMap<>(astr.length() + 1);
        // Iterate over each character to see if the same character exists in the map
        for (int i = 0; i < astr.length(); i++) {
            // The same character exists
            if (null! = map.get(astr.charAt(i)) && map.get(astr.charAt(i)) ==1) {
                return false;
            }
            // This character does not exist in map
            map.put(astr.charAt(i), 1);
        }
        return true;
    }

    public static void main(String[] args) {
        String astr = "JavaLib in Tangerine peel";
        StrIsUnique strIsUnique = newStrIsUnique(); System.out.println(strIsUnique.isUnique01(astr)); }}Copy the code

Method three

If we don’t have to resort to other data structures, how do we do that? Because uniqueness is required, there must be character comparisons. Solution 2 We used hash tables as data structures and only beat 27.28% of users in memory consumption.

Given that the string contains 26 lower-case characters, solution two is to put each character into the hash table, which is unique if there are no duplicate characters at each position in the hash table. So we can map each character to a binary array, by and, if the same position is 1, the result is 1, which means there are duplicate characters.

With an int mark that starts at 0, the binary form is 0000… 0000, iterate over each character, calculate the distance between character a and move_bit, and then use the left shift operator 1 << move_bit to create num with subscript 1 and the remaining subscripts 0. Num and mark; if the result is not 0, there are duplicate characters. If the result is 0, it indicates that the character has not occurred before. Assign the result of num and mark by or to mark, that is, set the corresponding subscript of this character to 1 in mark.

package com.chenpi;

import java.util.HashMap;
import java.util.Map;
import java.util.function.BinaryOperator;

/ * * *@DescriptionImplement an algorithm that determines whether all characters of a string s are different. *@Author Mr.nobody
 * @Date 2021/4/18
 * @Version1.0 * /
public class StrIsUnique {

    public boolean isUnique02(String astr) {
        // If the string is null or empty, there are no duplicate characters
        if (null == astr || 0 == astr.length()) {
            return true;
        }
        int mark = 0;
        int num = 0;
        // Iterate over each character
        for (int i = 0; i < astr.length(); i++) {
            num = 1 << (astr.charAt(i) - 'a');
            // Check whether the corresponding subscripts are 1, that is, whether the characters are the same
            if((mark & num) ! =0) {
                return false;
            }
            // Set the corresponding subscript to 1 in map
            mark |= num;
        }
        return true;
    }

    public static void main(String[] args) {
        String astr = "javalib";
        StrIsUnique strIsUnique = newStrIsUnique(); System.out.println(strIsUnique.isUnique02(astr)); }}Copy the code

Previous problem and next problem

LeetCode implements strStr()

Next question: LeetCode’s question of the day “Deciding whether to rearrange characters for each other”