Պոլինդրոմ (palindrome) բառեր

Բարև սիրելի ծրագրավորող (կամ ապագա ծրագրավորող)։

Այսօր կնայենք հարցազրույցների ժամանակ ամենատարածված խնդիրներից մեկը՝ պոլինդրոմ բառերի խնդիրը։

Սակայն մինչև առաջ անցնելը 2 կարևոր բան
֊ Խնդիրների լուծումները կլինեն JavaScript լեզվով,
֊ Ես ներկայացնում եմ խնդիրը լուծելու գաղափարները և չեմ բացատրելու, թե որ ֆունկցիան իրենից ինչ է ներկայացնում, սակայն կտեղադրեմ համապատասխան հղումները, որպեսզի դու ինքդ ուսումնասիրես դրանք:

Եթե սիրում ես խնդիրներ լուծել, ուրեմն արդեն լուծել ես այսպիսի խնդիր։ Կամ հարցազրույցի ժամանակ առընչվել ես այսպիսի խնդրի։

Նախ հասկանանք խնդիրը։
Ի՞նչ է իրենից ներկայացնում պոլինդրոմ բառը։ Պոլինդրոմ կոչվում են այն բառեր/թվերը, որոնք թե՛ աջից, թե՛ ձախից նույն կերպ են կարդացվում։ Այդպիսի բառերի օրինակներից են «շիշ», «Աննա» և նմանատիպ կառուցվածք ունեցող բառերը։ Իսկ թվերից «12321», «12344321» և նմանատիպ մնացած թվերը։

Սակայն ինչպե՞ս վարվել երբ բառի/թվի երկարությունը կենտ թիվ է։ Այսինքն մեջտեղում ունենալու ենք մի տառ, որը ոչ մեկի հետ չենք կարող ստուգել։ Պարզվում է, այս դեպքում մեջտեղի տառը ստուգելու կարիք չկա, որովհետև այն չի ազդում բառի պոլինդրոմության վրա։

Հիմա փորձենք հասկանանք, թե ինչպես կարող ենք լուծել այս խնդիրը։ Պարզվում է, դա այդքան էլ բարդ չէ։ Ուղղակի պետք է առաջին տառը/նիշը համեմատենք վերջից առաջին տառի/նիշի հետ։ Եթե տառերը/նիշերը նույնն են, անցնում ենք առաջ և երկրորդը համեմատում ենք վերջից երկրորդի հետ։ Այդ ամենը անում ենք այնքան, մինչև գտնենք այնպիսի տառերի/նիշերի զույգ, որոնք նույնը չեն։ Այդ դեպքում տրված բառը/թիվը կդադարի պոլինդրոմ լինելուց։ Հակառակ դեպքում, եթե չգտնենք այդպիսի զույգ, ուրեմն թիվը պոլինդրոմ է։

Ծրագրավորման տեսանկյունից ինչպե՞ս կարող ենք հասկանալ բառի/թվի պոլինդրոմությունը։

Գաղափարներից մեկը, որ գալիս է, այն է, որ վերցնենք երկու զանգված, մեկի մեջ տեղավորենք առաջին կեսի տառերը, մյուսի մեջ երկրորդ կեսի տառերը։ Հետո համեմատենք զանգվածների համապատասխան տառերը։

Եթե բառի երկարությունը կենտ թիվ է, ապա պետք է անել այնպես, որ այդ տառը ոչ մի զանգվածի մեջ չգտնվի, քանի որ այն գտնվում է հենց մեջտեղում և չի ազդում բառի պոլինդրոմության վրա։

Դե ինչ, անցնենք առաջ և դիտարկենք այս խնդիրը կոդի տեսանկյունից։

Ընդունենք, որ այս խնդրի դեպքում մեր ֆունկցիային միշտ string տիպի արժեք է փոխանցվելու, որը կարող է ունենալ թե՛ մեծատառ, թե՛ փոքրատառ տառեր։ Սակայն տառի մեծատառ և փոքրատառ լինելը չի ազդում պոլինդրոմության վրա։ Ընդունենք նաև այն, որ փոխանցվող արժեքը կարող է դարակ լինել (դատարկ stirng֊ը (""֊ը) կարող ենք պոլինդրոմ համարել)։

Կոդը տեղադրված է այս հղման մեջ

Այս լուծման օրինակում մենք հայտարարում ենք 2 զագնված։ firstHalf֊ի մեջ տեղավորում ենք բառի առաջին կեսի տառերը, իսկ secondHalf֊ի մեջ երկրորդ կեսի տառերը։

Երկրորդ զանգավծը շրջենք reverse() մեթոդի օգնությամբ։ Հետո ստուգենք firstHalf֊ի առաջին տառը secondHalf֊ի առաջին տառի հետ։ Հետո firstHalf֊ի երկրորդ տառը secondHalf֊ի երկրորդ տառի հետ և այդպես շարունակ։ Եթե գտնենք այնպիսի տառերի զույգ, որոնք նույնը չեն, դա նշանակում է, որ բառը պոլինդրոմ չէ։ Հակառակ դեպքում այն պոլինդրոմ է։

Իհարկե, այս տարբերակի վրա կարող ենք որոշակի փոփոխություններ կատարել, որոնք կարող են կոդը ավելի քիչ դարձնել, իսկ ալգորիթմը ավելի օպտիմալ։

Սակայն եկեք դիտարկենք լուծման այլ տարբերակ։

Կոդը տեղադրված է այս հղման մեջ

Ինչպես արդեն նշեցի, մենք պետք է ստուգենք տրված բառի առաջին մասը երկրորդ մասի հետ։ Այսինքն for loop֊ը կարող ենք իրականացնել բառի երկարության կեսի չափով (str.length/2): Որպեսզի կոդը ավելի պարզ լինի, ես charFromFirstHalf֊ին վերագրում եմ բառի առաջին կեսից վերցրած հերթական տառը, իսկ charFromSecondHalf֊ին վերագրում եմ բառի երկրորդ կեսից նրան համապատասխանող տառը։ Այդ տառերը toLowercase() մեթոդի միջոցով կդարձնենք փոքրատառ, քանի որ տառերի համեմատություն անելիս համեմատվում են տառերի ASCII կոդերը, որոնք ամեն սիմվոլի համար տարբեր են (օր․ "A" տառի ASCII կոդը 65 է իսկ "a" տառինը 97):
Քանի որ կոդը JavaSript լեզվով է և այստեղ զանգվածի ինդեքսավորումը սկսվում է 0֊ից, հետևաբար զանգվածի երկարության և զանգվածի վեջին էլեմենտի ինդեքսի թվերը իրարից 1֊ով տարբերվում են։ Այդ պատճառով երկրորդ կեսից համապատասխան ինդեքսը կվերցնեմ str.length-1-i ձևով։

Դե, ինչպես նշեցի, մեր վերցրած տառերը պիտի համեմատենք։ Եթե նրանք հավասար չեն, դա նշանակում է, որ բառը պոլինդրոմ չէ։ Տառերի հավասար չլինելու դեպքում կարող ենք ֆունկցիան դադարեցնել և վերադարձնել false արժեքը։

Հակառակ դեպքում, երբ բոլոր տարռերի զույգերը հավասար են, for loop֊ը հաջողությամբ կավարտվի և կանցնենք առաջ ու կվերադարձնենք true:

Այս նույն գաղափարը կարող ենք իրագործել նաև while֊ի օգնությամբ։ Այդ դեպքում մեր կոդը կունենա այս տեսքը։

Կոդը տեղադրված է այս հղման մեջ

Հույս ունեմ, այս նյութը քեզ օգնեց նոր գաղափարներ և նոր գիտելիք ստանալու հարցում։ Իսկ եթե ունես այնպիսի լուծման եղանակ, որը այստեղ նշված չէ, շատ ուրախ կլինեմ, եթե քո տարբերակը ուղարկես ինձ, այդպիսով փորձի փոխանակում կանենք։