DEV Community

Jasterix
Jasterix

Posted on • Updated on

Challenge-- Capitalize each word in a string

How is everyone holding up? The last few weeks have been completely unpredictable in the worst ways. So I can only hope that you are all maintaining your sanity, continuing the job search and making progress towards your goals step by step.

I took some time off from blogging to recenter in the midst of this craziness. But found myself wanting to blog about my progress with algos and understanding Big O Notation aka time/space complexity.

Found this YouTube playlist by KodingKevin which does the best job I've seen in breaking down this difficult subject. I've been working through the problems in this playlist one by one. Pausing the video to attempt the challenge, reviewing his solution and quizzing myself on the complexity before hearing Kevin's answer.

I just finished the Capitalize challenge with a different approach. Check out Kevin's solution and take a look at mine below. How could I make my solution more efficient?

Challenge:
  • Write a function that returns the provided string with the first letter of each word capitalized. Make sure the rest of the word is in lower case.
My initial questions (important in an interview setting):
  • Do I want to use Title Case (every word)or Sentence Case (first word only)? Response: Title Case
  • Do I need to be grammatically correct? Make sure "I" is always capitalized? Make sure "the", "and", etc are never capitalized? Response: Ignore grammar rules
My solution (pseudocode):
  1. Split string into an array of words
  2. Convert every first letter to uppercase
  3. Convert my words array to a string with .join()
  4. Return the new string
My solution (JavaScript):
function capitalize(str) {

  // Split string into an array of words
  const string = str.split(" ");
  const cased = [];

  // Convert every first letter to uppercase
  string.map((word) => {
    cased.push(word[0].toUpperCase() + word.slice(1).toLowerCase());
  });

  // Convert my words array to a string with .join()
  return cased.join(" ");
}
Enter fullscreen mode Exit fullscreen mode
Time / Space Complexity:
  • O(N) aka linear -- this is because our solution goes through every element of our string

Top comments (11)

Collapse
 
neradev profile image
Moritz Schramm • Edited

Here is my solution in JavaScript :)

const capitalize = (t) => t.replace(/(^|\s)[a-z]/g, (a) => a.toUpperCase());
Collapse
 
wisniewski94 profile image
Wiktor Wiśniewski

I don't know about this one, somehow @jasterix solution was more friendly to me. I'm not a fan of RegEx because it's really hard to memorize and easy to forget when you are not using it for a week or so (exaggerating)

Collapse
 
neradev profile image
Moritz Schramm

Luckily (or sometimes badly), everyone finds something different easier to read. I personally like the RegEx approach more, since it directly show what happens to which parts. I am quite used to read RegEx and find it more confusing to think again about what function is doing what and resulting in what.

Collapse
 
jasterix profile image
Jasterix • Edited

Very nice! Unfortunately I suck at RegEx :(

Would the Big-O of this be constant?

Collapse
 
neradev profile image
Moritz Schramm • Edited

This one should be O(n). I had the same question in mind and googled it. Never the less, I am actually a big fan of regex :D I have fun writing them.

Collapse
 
cyberhck profile image
Nishchal Gautam • Edited

This is mixing functional, I find it a bit weird, what I'd do:

function capitalize(str) {

  // Split string into an array of words
  const string = str.split(" ");

  // Convert every first letter to uppercase
  return string.map((word) => {
    return word[0].toUpperCase() + word.slice(1).toLowerCase();
  }).join(" ");
}

I'd also move the capitalize first letter to separate function to gain some performance

Collapse
 
nimonian profile image
Simon Haines

I was playing around with this a few ways in Python. I wondered if just passing through the characters once would be better than splitting and joining which passes through the words multiple times. First up, make a big string.

from time import time
a = 'hello this is my string it is lovely!'*10000
a = a.strip()

First try:

t = time()
A = a[0].upper()
for i in range(1,len(a)):
    c = a[i]
    A += c.upper() if (a[i-1] == ' ') else c
print(time() - t)

This takes 5.04s (3 s.f.). Maybe looking up the value of the string at a[i-1] is too slow, so here's another try using flags to speed things up:

t = time()
A = ''
flag = True
for c in a:
    if flag == True:
        c = c.upper()
        flag = False
    A += c
    if c == ' ':
        flag = True
print(time() - t)

The time becomes 4.44s (3 s.f.), so we've shaved a bit off. Then I tried the Python equivalent of @jasterix solution:

t = time()
A = ' '.join(w[0].upper() + w[1:] for w in a.split(' '))
print(time() - t)

The time... 0.0615s (3 s.f.). Now, although the first two pass through each character whereas the last one only passes through the words, surely split(' ') needs to examine each character to decide if it is ' ' or not? This got me thinking, so I tried:

A = ''
t = time()
for c in a:
    A += c
print(time() - t)

Just going through the string and adding each character to the end of an new string takes 4.20s (3 s.f.) seconds! Compared with

t = time()
A = ''.join(c for c in a)
print(time() - t)

which takes 0.0246s.

In short, I conclude that split() and join() are magic and I will use them for building strings over += in Python from now on, where possible!

Collapse
 
nazmulpcc profile image
Nazmul Alam

I don't think your solution is linear. Split and Join functions have time complexity too. A true O(n) solution would iterate over the string directly(only once) and make changes on the fly. Looping through the given string and capitalizing any character that has a space before can be a O(n) I think.

Collapse
 
neradev profile image
Moritz Schramm

Well, given split and join are also O(n) then you would have some complexity like 3n + x which still is O(n) since you would remove all constants.

Collapse
 
adam_cyclones profile image
Adam Crockett 🌀

text-transform: capitalize;

I cheeted

Collapse
 
tarun_geek profile image
Tarun Nagpal

So simple