Longest Word in Dictionary through Deleting

1. Description

2. Solution

• No sort

代码语言：javascript复制

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        int index = 0;
        int maxLength = 0;
        for(int i = 0; i <  d.size(); i  ) {
            int m = 0;
            int n = 0;
            while(m < s.size() && n < d[i].size()) {
                if(s[m] == d[i][n]) {
                    n  ;
                }
                m  ;
            }
            if(n == d[i].size() && (maxLength < d[i].size() || (maxLength == d[i].size() && d[i] < d[index]))) {
                index = i;
                maxLength = d[i].size();
            }
        }
        if(maxLength == 0) {
            return "";
        }
        return d[index];
    }
};

• Sort

代码语言：javascript复制

bool compare(string& a,string& b)
{
      return a.size() != b.size()?a.size() > b.size():a < b;
}

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        sort(d.begin(), d.end(), compare);
        for(int i = 0; i <  d.size(); i  ) {
            int m = 0;
            int n = 0;
            while(m < s.size() && n < d[i].size()) {
                if(s[m] == d[i][n]) {
                    n  ;
                }
                m  ;
            }
            if(n == d[i].size()) {
                return d[i];
            }
        }
        return "";
    }
};

• Faster(use find function)

代码语言：javascript复制

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        int index = 0;
        int maxLength = 0;
        for(int i = 0; i <  d.size(); i  ) {
            int charIndex = -1;
            int j = 0;
            for(j = 0; j < d[i].size(); j  ) {
                charIndex = s.find(d[i][j], charIndex   1);
                if(charIndex == -1) {
                    break;
                }
            }
            if(j == d[i].size() && (maxLength < d[i].size() || (maxLength == d[i].size() && d[i] < d[index]))) {
                index = i;
                maxLength = d[i].size();
            }
        }
        if(maxLength == 0) {
            return "";
        }
        return d[index];
    }
};

• Faster(use find function sort)

代码语言：javascript复制

bool compare(string& a,string& b)
{
      return a.size() != b.size()?a.size() > b.size():a < b;
}

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        sort(d.begin(), d.end(), compare);
        for(int i = 0; i <  d.size(); i  ) {
            int charIndex = -1;
            int j = 0;
            for(j = 0; j < d[i].size(); j  ) {
                charIndex = s.find(d[i][j], charIndex   1);
                if(charIndex == -1) {
                    break;
                }
            }
            if(j == d[i].size()) {
                return d[i];
            }
        }
        return "";
    }
};

function sort

0 人点赞