In this post we will solve LeetCode 171Excel Sheet Column Number problem using the Java programming language.
If interested in this problem, I suggest you go to the LeetCode website and read the description of the problem in case something has changed. If you are still interested please read on.
Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... Constraints: o 1 <= columnTitle.length <= 7 o columnTitle consists only of uppercase English letters. o columnTitle is in the range ["A", "FXSHRXW"]. Related Topics: o Math o String
The problem is relatively simple. We are given a string of uppercase characters each of which represents a digit in base 26. We need to compute the integer value associated with the string.
I will be solving the problem using Java and the VSCode IDE on a Windows computer. When I am satisfied with a version of the code and wish to submit it for evaluation, I will copy and paste it onto the online IDE provided by LeetCode. A simpler way is to develop the solution directly on the LeetCode website. I am not doing so because I wish to keep in the same source code file a test scaffold and the solution. Please note that the test code IS NOT PART OF THE SOLUTION!
public int titleToNumber(String columnTitle) { }
The signature for the function of interest matches well the problem description. It takes a string of uppercase characters which represents a column number in the spreadsheet and returns the associated binary value.
A main <<< columnTitle ==>A<== main <<< titleToNumber: 1 AB main <<< columnTitle ==>AB<== main <<< titleToNumber: 28 ZY main <<< columnTitle ==>ZY<== main <<< titleToNumber: 701 FXSHRXW main <<< columnTitle ==>FXSHRXW<== main <<< titleToNumber: 2147483647
Each test case is separated by two blank lines.
The first line contains the name of the column in the spreadsheet. Our test code seems to read the input line and assign the value to the `columnTitle` variable. The content of the variable is then displayed. This is done to make sure that all is well before calling the function of interest. This is part of the Test Driven Development approach I like to use when developing software in general.
It seems that the test code makes a call to the function of interest and then displays the corresponding column number.
/** * Test scaffold. * !!! NOT PART OF SOLUTIN !!! * @throws IOException */ public static void main(String[] args) throws IOException { // **** open buffered reader **** BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // **** read columnTitle string **** String columnTitle = br.readLine().trim(); // **** close buffered reader **** br.close(); // ???? ???? System.out.println("main <<< columnTitle ==>" + columnTitle + "<=="); // **** call function of interest and display result **** System.out.println("main <<< titleToNumber: " + titleToNumber(columnTitle)); }
The test scaffold is quite simple and follows the description of the test cases. At this point I do not have much else to add.
/** * Given a string columnTitle that represents the column title as appear in an Excel sheet, * return its corresponding column number. * * Runtime: O(n) - Space: O(1) * * Runtime: 1 ms, faster than 100.00% of Java online submissions. * Memory Usage: 38.7 MB, less than 95.39% of Java online submissions. * * 1002 / 1002 test cases passed. * Status: Accepted * Runtime: 1 ms * Memory Usage: 38.7 MB */ static public int titleToNumber(String columnTitle) { // **** initialization **** int columnNumber = 0; // **** compute column number - O(n) **** for (char ch : columnTitle.toCharArray()) { // **** shift value left one digit in base 26 **** columnNumber *= 26; // **** add current digit in base 26 **** columnNumber += ch - 'A' + 1; } // **** return column number **** return columnNumber; }
We start by declaring and initializing the `columnNumber` integer which will hold the value we will return with the column number.
We enter a loop in which we multiply the current value in the `columnNumber` by 26 to shift it left by one digit in base 26. Base 26 is being used because there are 26 uppercase characters in the English language.
We then need to add the value of the current character. Since `A` is the first character we need to subtract the value of `A` and compensate by 1 since the first character `A` is mapped to value 1 (not zero).
After the loop completes, we return the value in the `columnNumber` variable.
If you take a look at the comments section of this function you will find the associated execution time which seems to be pretty good!
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named ExcelSheetColumNumber.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John