Leetcode шешімінің соңғы сөзінің ұзындығы


Күрделілік дәрежесі оңай
Жиі кіреді Google
String

Проблемалық мәлімдеме

Бұл мәселеде көп сөз жол берілген және біз осы жолда кездесетін соңғы сөздің ұзындығын қайтаруымыз керек. Егер сөз болмаса, біз 0 мәнін қайтаруымыз керек.

мысал

s = "Hello World"
5

Түсініктеме: «Әлем» сөзінің ұзындығы 5-ке тең.

s = " "
0

Түсіндіру: сөз жоқ болғандықтан, жауап 0 болады.

жақындау

Бұл мәселені шешу үшін алдымен жолда орналасқан барлық бос орындарды екі ұшында да кесу керек. Содан кейін жолды бірінші таңбадан соңғы таңбаға дейін қайталау арқылы соңғы сөздің ұзындығын таба аламыз. Кесу үшін біз бірінші және соңғы таңбалардың индексін берілген жолда сәйкесінше сақтайтын екі «басталу» және «аяқталу» айнымалыларын қолдана аламыз.

 

Бірінші таңбаның индексін табу үшін 'start' = 0 айнымалысын инициализациялаңыз.
Енді жай ғана while циклін қолданыңыз да, айнымалының мәнін бірінші таңбаны алғанға дейін көбейтіңіз.
Дәл сол сияқты соңғы символ үшін айнымалыны n-1 инициализациялайды, мұндағы n - берілген жолдың өлшемі және оның мәнін while циклінде бірінші таңбаны алғанға дейін (аяғынан) аламыз.

егер start> end болса, онда бұл енгізу жолында ешқандай таңба жоқ, демек 0 дегенді білдіреді.
әйтпесе бізде нақты жол бар.

Соңғы сөздің ұзақтығы

Енді соңғы сөздің ұзындығын табу үшін біз нақты жолды соңынан бастап ешқандай бос кеңістік таппағанға дейін қайталанатын pos ауыспалы айнымалысын ала аламыз немесе біз жолдың бірінші таңбасына жетеміз.
Енді біз соңғы таңбалық индекс (айнымалы соңында сақталған) мен pos айнымалысында сақталатын ағымдағы индекс арасындағы айырмашылықты қайтарамыз.

Іске асыру

Соңғы сөздің ұзақтығына арналған C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;

int lengthOfLastWord(string s) 
{
        
        int n=s.size();
        if(n==0) return 0;
        
        int start,end;
        
        start=0;
        while(start< n && s[start]==' ') start++;      //left trim
        
        end=n-1;
        while(end >=0 && s[end]==' ') end--;         //right trim
        
        if(start>end) return 0;
        
        int pos=end;
        while(pos>=start)
        {
            if(s[pos]==' ') return end-pos;
            else pos--;
        }
        
        return end-pos;
        
}
int main() 
{
    string s="Hello World";
    
    cout<<lengthOfLastWord(s)<<endl;
    
  return 0; 
}
5

Соңғы сөздің ұзақтығына арналған Java бағдарламасы

import java.util.*;
import java.lang.*;

class LastWord
{  
    public static int lengthOfLastWord(String s) 
    {
        int n=s.length();
        if(n==0) return 0;
        
        int start,end;
        
        start=0;
        while(start< n && s.charAt(start)==' ') start++;    //left trim
        
        end=n-1;
        while(end >=0 && s.charAt(end)==' ') end--;      //right trim
        
        if(start>end) return 0;
        
        int pos=end;
        while(pos>=start)
        {
            if(s.charAt(pos)==' ') return end-pos;
            else pos--;
        }
        
        return end-pos;
    }
    
    public static void main(String args[])
    {
        String s="Hello World";
        System.out.println(lengthOfLastWord(s));
    }
}
5

Соңғы сөздің ұзақтылығының күрделілігін талдау

Уақыттың күрделілігі

O (n): Мұндағы n - енгізу жолының ұзындығы. Біз жолды бір цикл бойынша қайталаймыз және нашар жағдайда ол бірінші символға өтуі мүмкін.

Ғарыштың күрделілігі 

O (1): Кіріске тәуелсіз тұрақты жады жұмсалады.