Solution Explanation for LeetCode 1271: Hexspeak

This problem involves converting a decimal number to its "Hexspeak" representation. The process is as follows:

1. Convert to Hexadecimal: The decimal number (represented as a string num) is first converted to its hexadecimal equivalent.

2. Replace Digits: The hexadecimal representation is then modified by replacing all occurrences of '0' with 'O' and '1' with 'I'.

3. Validity Check: The resulting string is considered valid only if it contains only the characters 'A', 'B', 'C', 'D', 'E', 'F', 'I', and 'O'. If any other character is present, the function should return "ERROR".

Time and Space Complexity Analysis

The dominant operation in this algorithm is the conversion to hexadecimal which takes O(log n) time, where n is the decimal number. All other operations (replacements, and validity check) are linear in the length of the hexadecimal string, which is also proportional to log n. Therefore, the overall time complexity is O(log n).

The space complexity is determined by the size of the hexadecimal string, which is O(log n). This is because the number of digits in the hexadecimal representation of a number grows logarithmically with the size of the decimal number. Therefore, space complexity is O(log n).

Code Implementations with Explanations

The solutions below demonstrate the algorithm in several programming languages. Each solution follows the same steps but might differ slightly in syntax and built-in functions used.

Python

class Solution:
    def toHexspeak(self, num: str) -> str:
        hex_num = hex(int(num))[2:].upper() # Convert to hex, remove "0x" prefix, uppercase
        hex_num = hex_num.replace('0', 'O').replace('1', 'I') # Replace 0s and 1s
        valid_chars = set('ABCDEFIO') # Set of allowed characters
        if all(c in valid_chars for c in hex_num): # Check validity
            return hex_num
        else:
            return "ERROR"
 

Explanation:

• hex(int(num))[2:].upper() efficiently converts the decimal string to its uppercase hexadecimal representation and removes the "0x" prefix.
• .replace('0', 'O').replace('1', 'I') performs the digit replacements.
• all(c in valid_chars for c in hex_num) concisely checks if all characters are valid using a generator expression and all().

Java

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public String toHexspeak(String num) {
        String hex_num = Long.toHexString(Long.parseLong(num)).toUpperCase();
        hex_num = hex_num.replace("0", "O").replace("1", "I");
        Set<Character> valid_chars = new HashSet<>(Set.of('A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'));
        for (char c : hex_num.toCharArray()) {
            if (!valid_chars.contains(c)) return "ERROR";
        }
        return hex_num;
    }
}

Explanation:

• Long.toHexString(Long.parseLong(num)).toUpperCase() converts to hex, similar to the Python approach.
• A HashSet is used for efficient character lookup during the validity check. Iterating through the toCharArray() allows for checking each character individually.

C++

#include <algorithm>
#include <sstream>
#include <string>
#include <set>
 
class Solution {
public:
    string toHexspeak(string num) {
        long long n = stoll(num);
        stringstream ss;
        ss << hex << n;
        string hex_num = ss.str();
        transform(hex_num.begin(), hex_num.end(), hex_num.begin(), ::toupper); //Uppercase
        for (char &c : hex_num){
            if (c == '0') c = 'O';
            else if (c == '1') c = 'I';
            else if (c < 'A' || c > 'F') return "ERROR";
        }
        return hex_num;
    }
};

Explanation:

• stoll converts the decimal string to a long long integer.
• stringstream is used for hexadecimal conversion.
• transform converts the string to uppercase.
• The for loop iterates and performs the replacement and validity checks in place

Go

import (
	"fmt"
	"strconv"
	"strings"
)
 
func toHexspeak(num string) string {
    n, _ := strconv.ParseInt(num, 10, 64)
    hexNum := strings.ToUpper(fmt.Sprintf("%x", n))
    hexNum = strings.ReplaceAll(hexNum, "0", "O")
    hexNum = strings.ReplaceAll(hexNum, "1", "I")
    validChars := "ABCDEFIO"
    for _, c := range hexNum {
        if !strings.ContainsRune(validChars, c) {
            return "ERROR"
        }
    }
    return hexNum
}

Explanation:

• strconv.ParseInt converts the decimal string to an integer.
• fmt.Sprintf("%x", n) converts to hexadecimal, similar to other examples.
• strings.ContainsRune checks if the character is present in the valid characters string.

These detailed explanations and code examples provide a comprehensive understanding of how to solve the Hexspeak problem efficiently and correctly in various programming languages. Remember to choose the language that best fits your needs and coding style.