ReSQL.ru
     
powered by simpleCommunicator - 2.0.36     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Решаю задачи для leetcode
4 сообщений из 29, страница 2 из 2
  2  все
Решаю задачи для leetcode
    #39784305
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Не могу решить задачу 126. ( https://leetcode.com/problems/word-ladder-ii/)

Нужно перевести этот код с java на php.

 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
        
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        
        if(wordList.isEmpty())  return res;
        HashSet<String> set = new HashSet<>();
        HashSet<String> unvisited = new HashSet<>(wordList);
        set.add(beginWord);
        unvisited.remove(beginWord);
        boolean found = false;
        while(!set.isEmpty()){
            if(found)   break;
            HashSet<String> temp = new HashSet<>();
            for(String s: set){
                for(int i=0; i<s.length(); i++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a'; c<='z'; c++){
                        sb.setCharAt(i, c);
                        String newWord = sb.toString();
                        if(unvisited.contains(newWord)){
                            if(newWord.equals(endWord))
                                found=true;
                            temp.add(newWord);
                            
                            //building the neighbour map
                            if(map.containsKey(newWord))
                                map.get(newWord).add(s);
                            else{
                                List<String> neighbours = new ArrayList<>();
                                neighbours.add(s);
                                map.put(newWord, neighbours);
                            }
                        }
                    }
                }
            }
            unvisited.removeAll(temp);
            set = temp;
        }
        
        backTrace(beginWord, endWord);
        return res;
    }
    
    private void backTrace(String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            list.add(0, beginWord);
            res.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        if(map.containsKey(endWord)){
            list.add(0, endWord);
            for(String pre: map.get(endWord)){
                backTrace(beginWord, pre);
            }
            list.remove(0);
        }
    }
}



Хорошего Вам дня!
...
Рейтинг: 0 / 0
10.03.2019, 20:25
| Ответить | Цитировать | Написать  
Решаю задачи для leetcode
    #39789877
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Решил 150 задач!

Хорошего Вам дня!
...
Рейтинг: 0 / 0
22.03.2019, 07:03
| Ответить | Цитировать | Написать  
Решаю задачи для leetcode
    #39936166
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Valentin Kolesnikov
Не могу решить задачу 126. ( https://leetcode.com/problems/word-ladder-ii )

Нужно перевести этот код с java на php.

 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
        
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        
        if(wordList.isEmpty())  return res;
        HashSet<String> set = new HashSet<>();
        HashSet<String> unvisited = new HashSet<>(wordList);
        set.add(beginWord);
        unvisited.remove(beginWord);
        boolean found = false;
        while(!set.isEmpty()){
            if(found)   break;
            HashSet<String> temp = new HashSet<>();
            for(String s: set){
                for(int i=0; i<s.length(); i++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a'; c<='z'; c++){
                        sb.setCharAt(i, c);
                        String newWord = sb.toString();
                        if(unvisited.contains(newWord)){
                            if(newWord.equals(endWord))
                                found=true;
                            temp.add(newWord);
                            
                            //building the neighbour map
                            if(map.containsKey(newWord))
                                map.get(newWord).add(s);
                            else{
                                List<String> neighbours = new ArrayList<>();
                                neighbours.add(s);
                                map.put(newWord, neighbours);
                            }
                        }
                    }
                }
            }
            unvisited.removeAll(temp);
            set = temp;
        }
        
        backTrace(beginWord, endWord);
        return res;
    }
    
    private void backTrace(String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            list.add(0, beginWord);
            res.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        if(map.containsKey(endWord)){
            list.add(0, endWord);
            for(String pre: map.get(endWord)){
                backTrace(beginWord, pre);
            }
            list.remove(0);
        }
    }
}





Так и не смог решить эту задачу на php.

Хорошего вам дня!
...
Рейтинг: 0 / 0
11.03.2020, 08:01
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Решаю задачи для leetcode
    #40067632
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Valentin Kolesnikov
Не могу решить задачу 126. (https://leetcode.com/problems/word-ladder-ii/)

Нужно перевести этот код с java на php.

 
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
        
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        
        if(wordList.isEmpty())  return res;
        HashSet<String> set = new HashSet<>();
        HashSet<String> unvisited = new HashSet<>(wordList);
        set.add(beginWord);
        unvisited.remove(beginWord);
        boolean found = false;
        while(!set.isEmpty()){
            if(found)   break;
            HashSet<String> temp = new HashSet<>();
            for(String s: set){
                for(int i=0; i<s.length(); i++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a'; c<='z'; c++){
                        sb.setCharAt(i, c);
                        String newWord = sb.toString();
                        if(unvisited.contains(newWord)){
                            if(newWord.equals(endWord))
                                found=true;
                            temp.add(newWord);
                            
                            //building the neighbour map
                            if(map.containsKey(newWord))
                                map.get(newWord).add(s);
                            else{
                                List<String> neighbours = new ArrayList<>();
                                neighbours.add(s);
                                map.put(newWord, neighbours);
                            }
                        }
                    }
                }
            }
            unvisited.removeAll(temp);
            set = temp;
        }
        
        backTrace(beginWord, endWord);
        return res;
    }
    
    private void backTrace(String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            list.add(0, beginWord);
            res.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        if(map.containsKey(endWord)){
            list.add(0, endWord);
            for(String pre: map.get(endWord)){
                backTrace(beginWord, pre);
            }
            list.remove(0);
        }
    }
}



Хорошего Вам дня!


Решение для задачи

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
class Solution {

    /**
     * @param String $beginWord
     * @param String $endWord
     * @param String[] $wordList
     * @return String[][]
     */
    function findLadders($beginWord, $endWord, $wordList) {
        $maskToWords = [];
        $wordToMasks = [];
        $closestWords = [];
        $allwords = $wordList;
        $allwords[] = $beginWord;
        foreach($allwords as $word){
            for($i=0;$i<strlen($word);$i++){
                $mask = $word;
                $mask[$i] = '_';
                $maskToWords[$mask][$word] = true;
                $wordToMasks[$word][$mask] = true;
            }
        }
        foreach($allwords as $word){
            foreach($wordToMasks[$word] as $mask => $notUsed){
                foreach($maskToWords[$mask] as $linkedWord => $notUsed){
                    $closestWords[$word][$linkedWord] = true;
                }
            }
        }
        unset($maskToWords);
        unset($wordToMasks);
        unset($allwords);
        $queue = new SplQueue();
        $visitedNodes = [];
        return (new Node($beginWord, $visitedNodes))->breadthFirstSearch($queue,$endWord,$closestWords);
    }
}

class Node {
    private $name;
    private $distance;
    private $parent;
    private $visitedNodes;
    function __construct($name, &$visitedNodes, $parent = null, $distance = 1){
        $this->name = $name;
        $this->parent = $parent;
        $this->distance = $distance;
        $this->visitedNodes = &$visitedNodes;
    }
    private function getNextNodes(&$closestWords){
        $nodes = [];
        foreach($closestWords[$this->name] as $linkedWord => $notUsed){
            if(!isset($this->visitedNodes[$linkedWord])){
                $nodes[] = new Node($linkedWord, $this->visitedNodes, $this, $this->distance+1);
            }
        }
        return $nodes;
    }
    private function getPath(){
        $node = $this;
        $path = new SplDoublyLinkedList();
        while($node){
            $path->unshift($node->name);
            $node = $node->parent;
        }
        $pathArray = [];
        foreach($path as $item){
            $pathArray[] = $item;
        }
        return $pathArray;
    }
    function traverse($queue,&$closestWords){
        $this->visitedNodes[$this->name] = true;
        foreach($this->getNextNodes($closestWords) as $node){
            $queue->enqueue($node);
        }
    }
    function breadthFirstSearch($queue,$endWord,&$closestWords){
        $this->traverse($queue,$closestWords);
        $paths = [];
        $bestDistance = null;
        while(!$queue->isEmpty()){
            $nextNode = $queue->dequeue();
            if(!is_null($bestDistance) && $bestDistance < $nextNode->distance)
                break;
            if($nextNode->name===$endWord) {
                if(is_null($bestDistance))
                    $bestDistance = $nextNode->distance;
                $paths[] = $nextNode->getPath();
            }
            $nextNode->traverse($queue,$closestWords);
        }
        return $paths;
    }
}
...
Рейтинг: 0 / 0
30.04.2021, 15:14
| Ответить | Цитировать | Написать  
4 сообщений из 29, страница 2 из 2
  2  все
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Решаю задачи для leetcode
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=23&startmsg=39784305&tid=1459482]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 43ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 40ms
get tp. blocked users:
 1ms
others: 13ms
total:  143ms
созд. / загр.: 143ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]