Using the array to record the occurrence of each character beats 96%


  • 1
    S
    public class Solution {
        public boolean canPermutePalindrome(String s) {
            int[] arr = new int[128];
            for(int i=0; i<s.length(); i++){
                int num = (int)s.charAt(i);
                arr[num]++;
            }
            int count = 0;
            for(int i=0; i<128; i++){
                if(arr[i]%2==1) count++;
                if(count>1) return false;
            }
            return true;
        }
    }

  • 0
    H
    This post is deleted!

  • 0
    S

    If the string length is even number, there must be even number of characters whose occurrence is odd(If only one occurrence is odd, then the whole string length should be odd). If that number is larger than 1, then it will not be palindrome, if it is smaller than 1, it should be 0 which is a palindrome.


  • 0
    S

    You should be able to just do arr[s.charAt(i)] instead of making an arbitrary int variable to store that char's value.


  • 0
    S

    I think the two lines of code
    int num = (int)s.charAt(i);
    arr[num]++;
    is what you mean here.


  • 0
    S

    You are correct.


  • 0
    S

    Thank you : )


  • 0

    This is terribly broken because it will fail on any characters outside of US-ASCII.


  • 0
    S

    Yes, that's the way why we should ask the interviewer to clarify what kind of encoding style is in this case, whether it is ASCII or Unicode.


  • 0

    Er, this is Java, right? Java is always Unicode, as far as encoding is concerned. So we would like to know what characters are actually allowed in the input string, not which encoding is used. An interviewer won't be happy if we mix up these concepts.


  • 0
    S

    Yes, JVM always use the Unicode as its encoding style. JVM converts ASCII into Unicode before compiling. But the encoding style still should be a reasonable question. It is possible that we enter our java program in an environment that stores ASCII which will be converted to Unicode internally in JVM. Strictly speaking, JVM only converts the literals and comments into Unicode since the first 128 characters of Unicode are ASCII. Moreover, the JDK we are talking about comes from SUN and there exists other JDKs which might apply only to ASCII.


  • 0

    Isn't Unicode the standard thing in Java? So if some other JDK doesn't use it, it's not strictly a Java DK any more? And why only literals and comments? Do you know that Java does allow to use any letters in identifiers, so I can literally name some class クラス and it will compile just fine? Not to forget also that our data can come from somewhere outside the program (entered by the user, for example).


  • 0
    S

    I made a mistake that's identifier not literals. How the JVM uses the encoding is defined by the JDK and there exists some JDKs from Borland and Symantec. There is no requirements that a JDK must use Unicode but the Sun JDK uses the Unicode and that's where our main documents comes from. Anyway, it is possible that we enter our java program in an environment that stores ASCII and it is a reasonable question to inquire the interviewer about the encoding of the code-entering environment.


  • 0

    What exactly do you mean by code-entering environment? It doesn't matter where you enter your code, it matters where the input data comes from.


  • 0
    S

    I think the input data comes in two ways. One could integrate the input data with the customer program in a java file and in this case the input data has the same encode with the java file and of course the input data can have its own file but still needs encoding. Another is to enter the input data at the run time and the default encoding for command line in Windows and Mac is ASCII as far as I am concerned. Thus clarifying the encode is a fair question to come up with.


  • 0

    What I'm still confused with is the Unicode issue. No matter which JDK, compiler, environment or I/O conversion, once inside JVM it can be only UTF-16 (according to String API docs). So it doesn't really matter now what encoding it was before it was converted to String, does it? What does matter, though, is what character set that particular encoding uses. But character sets can be shared between encodings. For example, it could be something as crazy as EBCDIC, but properly converted to String, it will be indistinguishable from ASCII.


  • 0
    S

    You are right, the JVM is UTF-16. However, if the text entering environment is ASCII, it will messed up those characters in Unicode. And when the JVM load this files it cannot distinguish the original Unicode because of the mess up.


  • 0

    That's unless someone specified the input encoding explicitly in order to properly convert it to UTF-16.


  • 0
    S

    Yes, but it's still worth asking about the encoding of the environment in order to make it clear. Because if the encoding is ASCII, it is less likely that the programmer write Unicode characters in the program.


  • 0

    This kind of logic produces a lot of code that unexpectedly breaks in the international environments. If I was interviewing a candidate for programmer, I'd immediately become suspicious if they started to talk about encodings in Java unless it's about I/O or explicit conversion. That's because I actually saw a lot of Java programmers thinking the old C way that String is actually bytes in some encoding, so they were saying things like "Look, I've just read a file in Cp1251 encoding, so my String should be Cp1251, but it seems to be UTF-8, why?" when it was neither. But, nevertheless, I guess it's OK to ask questions about encodings if you actually know what you're talking about.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.