Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 27.01.2014, 20:17   #1
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Universe
Age: 36
Posts: 3,413
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default Yet another interview puzzle (anagrams)

Часто задаваемая задача при интервью:
Проверка строк на идентичность. То есть, выражаясь математическим языком, задача сводится к определению является ли одна строка конечной перестоновкой другой, такие строки называются анаграмами.

Пример:
торс
сорт
трос
рост

Наиболее оптимальным решением мне видется следующая реализация:

Code:
#include <algorithm>
#include <iostream>
#include <string>
 
typedef unsigned int uint;
 
inline bool notZero(uint n) {
    return n!=0;
}
 
bool areAnagrams(const std::string& s1, const std::string& s2) {
    uint hist[256] = {0};
    if(s1.length() != s2.length()) return false;
    for(std::string::const_iterator i = s1.begin(), j = s2.begin(); i != s1.end(); ++i, ++j) {
        ++hist[(uint)*i];
        --hist[(uint)*j];
    }
    return std::find_if(hist, hist + 256, notZero) == hist + 256;
}
 
int main() {
    std::cout << areAnagrams("google", "elgoog");
}
Если есть непонятки в реализации спрашиваете - разъясню.
Шкурой чую, что оптимальнее переписать - мёртвый номер.
Так, что особо пытливым умам предлагается просто переписать иначе.
Reply With Quote
Reply

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Interview (in french) arabaliozian Comments 0 28.11.2009 20:04
interview arabaliozian Comments 0 16.08.2008 17:49
The Interview with God PsilocybeLarvae English Only 5 29.11.2005 16:56
[JAVA GAME MOTOROLA VXX] Puzzle Bobble acid Mobile Phones and Gadgets 0 25.07.2005 21:16
Fallout 3 interview Yerkanian Games 0 18.07.2002 19:40


На правах рекламы:
реклама

All times are GMT. The time now is 14:01.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.