This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

preface

The length of the last word in question 58 is as follows:

You are given a string s, consisting of several words separated by space characters. Returns the length of the last word in the string.

A word is the largest substring that consists only of letters and does not contain any space characters.

Example 1:

Input: s = "Hello World" Output: 5Copy the code

Example 2:

Input: s = "fly me to the moon" output: 4Copy the code

Example 3:

Input: s = "Luffy is still joyboy" Output: 6Copy the code

A, thinking

The length of the last word contains one important piece of information: words are separated by Spaces

Our goal is to find the length of the last word, so there are two ways to find the length of the last word.

Double pointer (front to back)

Traversing the string from front to back, left and right both start at 0. There are two cases

  • Hit a space character If:right > left, records the result. Let both Pointers point to the current position, i.eleft = right = i
  • Encounter letters: now letright++Can be

Analog count (from back to front)

Because the length of the last word is found, this scheme is more efficient. Once the length of the last word is found, the loop stops immediately.

The string is traversed backwards, with count starting at 0. There are two cases

  • Encounter letters: now letcount++The count can be added by one
  • Encounter blank: if at this timecount > 0Straight out of the loop and backcountvalue

For example

Choose option 2 here, and use s = “Luffy is still Joyboy” in example 3 as an example

  1. i=20At this time,s.charAt(20) == 'y'Counting,count = 1
  2. i=19At this time,s.charAt(19) == 'o'Counting,count = 2
  3. i=18At this time,s.charAt(18) == 'b'Counting,count = 3
  4. i=17At this time,s.charAt(17) == 'y'Counting,count = 4
  5. i=16At this time,s.charAt(16) == 'o'Counting,count = 5
  6. i=15At this time,s.charAt(15) == 'j'Counting,count = 6
  7. i=14At this time,s.charAt(14) == ' ', the loop is broken
  8. Return count value6Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

Double pointer

    /** * simple double pointer (front to back) */
    public int lengthOfLastWord1(String s) {
        int len = s.length();
        int left = 0;
        int right = 0;
        int ret = 0;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == ' ') {
                if (right > left)
                    ret = right - left;
                left = right = i;
            } else{ right ++; }}return right > left ? right - left : ret; // Maybe the last word didn't count
    }
Copy the code

Simulation count

    /** * simple count (from back to front) */
    public int lengthOfLastWord(String s) {
        int len = s.length();
        int count = 0;
        for (int i = len -1; i > -1; i--) {
            if (s.charAt(i) == ' ') {
                if (count > 0)
                    break;
            } else{ count ++; }}return count;
    }
Copy the code

The test code

    public static void main(String[] args) {
        String str = "luffy is still joyboy";
        new Number58().lengthOfLastWord(str);
    }
Copy the code

The results of

The result here is the result of the analog count, and the beat rate of the dual pointer is only in the teens.

Third, summary

I have already brushed more than half of one hundred questions unconsciously

Thank you to see the end, very honored to help you ~♥