Not gonna lie, been chipping away at this for almost an hour and I can't figure out how to solve it, let alone elegantly:

https://leetcode.com/problems/...

Doesn't look too difficult. Basically looping over and for each prependable character, check whether the following one is a higher one so that it will be subtracted, otherwise add it to what was there before.

What did you tried ?

What language did you pick ?

In c# (my main) I would create a dictionary with the mapping then iterate over all the string, get the correct value and add them up.

@rEaL-jAsE Enum will work too, but I've never found a really usefull usecase for it.

Most of the time I use dictionaries or lists (So I can use Linq)

Not sure if you can do something like

string s = 'I';

enum.s (where s = a variable)

My main issue was simulataneously handling the special double character cases but also skipping the correct amount AND ensuring the first and last characters are read correctly... sigh.

But then I did a 'hard' challenge for finding the median of two arrays in like 3 minutes and got "better than 80%" of submissions... so idk

Again proving why leetcode is miserable, if you get stuck on one everyone thinks your shit when there are literally thousands of challenges like that.

1. start with curChar empty, curcharCount 0, curVal 0, finalVal 0

2. enter loop over string.

3. if curChar equals string char, curCharCount++

4. if not, then:

4.a. if charVals[string[i]] is larger than charVals[string[curChar] then

curVal = -curCharCount * charVals[curChar]

4.b. if charVals[string[i]] is smaller than or equal charVals[string[curChar]] then

curVal = curCharCount * charVals[curChar]

4.2. finalVal += curVal

5. curChar = string[i] (this is the last step in the loop)

6. have another dictionary, probably <string, int>, where you "log" the values of each part when you encounter it, so if curChar doesn't exist in it, add. if sequence of lower value curChars followed by larger value curChar doesn't exist, add.

something like this should work, methinks?

does it count as elegant?

Here's my corrected solution, the previous one had a copy/paste bug in isPrefix:

dude i'm actually gonna try and do it.

congratulations, you were the motivation for me to want to even open the IDE, after about a month and a half that I didn't even want to think about touching it.

I would have done something like this in C#

(It passed all the test ;) )

lol, it actually works, it seems...?

not entirely as i described it, but still, to be honest, I didn't actually expect it to work =D

(edit: oh, that empty char in dictionary is a vestige of when I wasn't actually setting curChar on the first char of the string at first, so you could delete that, as well as line 30. i'm just being sloppy)

@Grumm

dammit, yours is shorter

(but less understandable for me personally)

@Fast-Nop

you're making it too complicated with the isPrefix function, imo.

@Midnight-shcode Yeah, the comparison would have worked as well, but I just hacked down the requirements without even thinking.

@Midnight-shcode

Runtime: 108 ms, faster than 37.80% of C# online submissions for Roman to Integer.

Memory Usage: 37.1 MB, less than 45.63% of C# online submissions for Roman to Integer.

damn, I don't even wanna see the actual top optimized versions then. must be awful to read =D

@rEaL-jAsE It is great and not only for database queries :)

I also work 90% with dynamic arrays so I use every usefull bit possible.

@Midnight-shcode mine was :

Runtime: 111 ms, faster than 34.19% of C# online submissions for Roman to Integer.

Memory Usage: 36.9 MB, less than 58.32% of C# online submissions for Roman to Integer.

For my it is pretty understandable how it works.

What part is hard ?

(I noticed that you don't check if the char is in the array. In this case, it may not break, but adding one wrong letter and yours will break because charVals['Y'] does not exists)

The performance numbers don't really mean anything. I submitted an identical solution two times in a row, with the isPrefix eliminated:

Runtime: 4 ms, faster than 90.96% of C online submissions for Roman to Integer. Memory Usage: 6 MB, less than 30.22% of C online submissions for Roman to Integer.

18 ms, faster than 15.37% of C online submissions for Roman to Integer. Memory Usage: 5.7 MB, less than 99.91 of C online submissions for Roman to Integer.

It seems that Leetcode can't even benchmark properly.

I would use a recursive function, starting with the highest value letter, if there a values on the left side, recurse and subtract the returned value, if there are one on the right, recurse and add.

And i would use a more readable code style. I can't read anything if { and } are not aligned as they should be.

@Grumm

that condition was harder to parse for me, but... it's really just the difference between actually reading it with attention (and then I get it, yeah), or just skimming it "i know what this is supposed to do but it seems kinda messy so I'm not sure if it really does that"...

yeah, in my version, i'm more verbose about it, so basically i am able to understand all of my code just by skimming it, no need to read any part of it with attention... less text that reads a bit slower, or more text that reads a bit faster, is the difference for me =D

This was kinda fun.

here is mine - not optimized in any way, but pretty simple and readable:

https://leetcode.com/submissions/...

Btw., the fastest letter to numeric value conversion would not be a switch case, but a 256 entry static array of int that is all zeros except for the ASCII positions of the letters. Then look up the value, but cast to unsigned char first just in case char happens to be signed.

@Fast-Nop oh yeah.
but the memory overhead... =D

@Midnight-shcode 512 bytes if using int16_t, or 1024 bytes if int is 32 bit wide. The main drawback is rather that I think it's somewhat hacky to abuse char for calculation. Unless speed requires it, then it's fine. :)

@Fast-Nop Yeah, I remember making sin and cos table lookups. I am glad most things are fast enough to not need to do that now. I suppose embedded it might still be needed.

But look at all of these solutions... does anyone really think it should have been classified as "easy"?

@fullstackchris Mapping individual characters into numbers is obvious, and checking whether "this" character and the next one form a digram as specified is literally just typing down the spec. The rest is syntactic sugar of whatever programming language you use.

@Fast-Nop yeah i mean i know the memory FOOTPRINT for such an array is still tiny (in today's context), but the memory OVERHEAD... as in... you're taking up 256 ints, just to have fast access to 6 or 8 ints of actual useful data,and the rest is useless nothing.

@Midnight-shcode Sure, but it spares any comparison and is branchless, which is important on modern CPUs.

You could also get away with less that 256, given that the spec said the input is valid Roman numbers. So you don't strictly need anything above 'X', but I'd prefer to make it robust with all inputs.

@Fast-Nop btw do you thibk the whole array would be loaded into cpu cache, or would there still be cache misses due to only partially caching the array and due to how staggered the actual usable values are across it?

@Midnight-shcode Provided that this routine would be used frequently enough, I don't see any issue even if you use 256 plain int (32 bit on PCs) - 1k is nothing compared to the megabytes of cache that we have.

For example, check out https://create.stephan-brumme.com/c... with different CRC lookup tables where the slicing approaches with 16k tables perform a lot better on large data than the standard 1k table by Sarwate or the half-byte approach with 64 byte table. The latter may still be worthwhile on very small microcontrollers, though.

@Fast-Nop well, this comment flew wayyyy off into the distance faraway from my actual knowledge, but the "yeah, no problem with cache misses" part i still get :)

The trick is to solve it right to left, this way you can save the previous value and know if the current value is + or minus.

E.g. IV

First (rightmost) is always + so
+5
Next is 1 but since lower than the current highest known value it is -1
+5 -1 = 4

Other example XXII
First +1
Second +1
Third +10
Forth +10
22

@KDSBest funny, all of us here solved it left to right and had no issues knowing whether current value should be plus or minus

@Midnight-shcode That's why I gave ++ to it, because it's an interesting different perspective. :)

@Demolishun @Midnight-shcode @Fast-Nop I honestly didn't know that something like IIX doesn't exist.

@KDSBest I wonder if it is faster ?

We go from left to right and just do the same +/- value. Like :

E.g. IV

First is lower so we do

-1

-1+5 = 4

@KDSBest Me either.